Why this approach is suboptimal: The time complexity is roughly $O(N \cdot M)$, where $N$ is the number of recipes and $M$ is the total number of ingredients across all recipes. In the worst-case scenario (a long chain where Recipe A allows Recipe B, which allows Recipe C, etc.), we might iterate through the list of recipes $N$ times. For large inputs, this redundant checking leads to Time Limit Exceeded (TLE) or poor performance compared to linear solutions.

Core Insight for Find All Possible Recipes from Given Supplies

The key intuition is to view ingredients and recipes as nodes in a graph. The relationship "Recipe A requires Ingredient B" can be modeled as a directed edge from B to A ($B \to A$). This direction signifies that having B contributes to unlocking A.

Using this model, the problem transforms into finding all nodes that can be reached and "processed" starting from the initial set of zero-dependency nodes (the supplies).

Key Mapping to Kahn's Algorithm:

1. In-Degree: The number of ingredients a recipe is currently missing.
2. Graph Edges: An adjacency list where a key is an ingredient (or a recipe acting as an ingredient) and the values are the recipes that require it.
3. Queue: A processing queue initially populated with the given supplies.

By processing the supplies, we "unlock" dependencies. Every time we process an item, we look at the recipes that need it and decrement their in-degree count. If a recipe's in-degree drops to 0, it means all its ingredients are available. We then add this recipe to the queue, allowing it to unlock further recipes.

This approach efficiently handles cascades of recipes (e.g., Bread $\to$ Sandwich $\to$ Burger) and naturally handles cycles (e.g., A needs B, B needs A) by simply never reducing their in-degrees to zero.

Algorithm Strategy: Graph BFS - Topological Sort (Kahn's Algorithm)

We will implement Kahn's Algorithm to solve this problem efficiently.

1. Graph Construction:

   • Create an adjacency list (graph) where graph[item] contains a list of recipes that require item.
   • Create an in_degree map where in_degree[recipe] stores the count of ingredients needed for that recipe.

2. Initialization:

   • Populate the graph and in_degree map by iterating through the recipes and ingredients input arrays.
   • Initialize a queue (specifically a Deque in Python/Java or std::queue in C++) with the initial supplies. These are our starting nodes with effectively "zero unmet dependencies."

3. BFS Traversal:

   • While the queue is not empty:
     • Dequeue the current item (ingredient or created recipe).
     • Iterate through all neighbors in graph[current_item] (recipes that need this item).
     • Decrement the in_degree of each neighbor.
     • Constraint Check: If a neighbor's in_degree becomes 0, it means the recipe is now possible. Add it to the queue and to our result list.

4. Output:

   • Return the list of created recipes.

Execution Flow

Let's trace the algorithm with a simple example: recipes = ["bread", "sandwich"], ingredients = [["flour"], ["bread", "meat"]], supplies = ["flour", "meat"].

1. Build Graph & In-Degrees:

   • in_degree: {"bread": 1, "sandwich": 2}
   • graph: {"flour": ["bread"], "bread": ["sandwich"], "meat": ["sandwich"]}

2. Initialize Queue:

   • Queue contains ["flour", "meat"] (from supplies).

3. Process "flour":

   • Pop "flour".
   • Neighbors of "flour": ["bread"].
   • Decrement in_degree["bread"] from 1 to 0.
   • in_degree["bread"] is 0. Add "bread" to Queue and Result.
   • Queue: ["meat", "bread"]. Result: ["bread"].

4. Process "meat":

   • Pop "meat".
   • Neighbors of "meat": ["sandwich"].
   • Decrement in_degree["sandwich"] from 2 to 1.
   • Queue: ["bread"].

5. Process "bread":

   • Pop "bread".
   • Neighbors of "bread": ["sandwich"].
   • Decrement in_degree["sandwich"] from 1 to 0.
   • in_degree["sandwich"] is 0. Add "sandwich" to Queue and Result.
   • Queue: ["sandwich"]. Result: ["bread", "sandwich"].

6. Process "sandwich":

   • Pop "sandwich".
   • Neighbors: None.
   • Queue empty.

7. Final Output: ["bread", "sandwich"].

Proof of Correctness

The algorithm is correct based on the invariant of Topological Sort. A node (recipe) is only added to the queue when its in-degree reaches zero. The in-degree represents the count of unsatisfied dependencies.

1. Base Case: We start with supplies, which are items that exist unconditionally (dependencies satisfied).
2. Inductive Step: When we process an item $U$, we effectively "supply" it to all recipes $V$ that depend on $U$. Decrementing the in-degree of $V$ correctly reflects that one less ingredient is needed.
3. Termination: A recipe is added to the result set if and only if all its specific ingredients have been processed.
4. Cycle Handling: If a set of recipes forms a cycle (A needs B, B needs A), their in-degrees will never reach zero because the dependencies are circular. They will correctly remain unvisited.

Reference Implementation

C++ Solution for LeetCode 2115

cpp
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        // Graph: ingredient -> list of recipes that need it
        unordered_map<string, vector<string>> graph;
        // In-degree: recipe -> count of missing ingredients
        unordered_map<string, int> in_degree;
        
        // Initialize in-degrees for all recipes
        for (const string& recipe : recipes) {
            in_degree[recipe] = 0;
        }

        // Build the graph
        for (int i = 0; i < recipes.size(); ++i) {
            string recipe = recipes[i];
            for (const string& ingredient : ingredients[i]) {
                graph[ingredient].push_back(recipe);
                in_degree[recipe]++;
            }
        }

        // Queue for Kahn's Algorithm, initialized with supplies
        queue<string> q;
        for (const string& supply : supplies) {
            q.push(supply);
        }

        vector<string> result;
        
        while (!q.empty()) {
            string current = q.front();
            q.pop();

            // If current item is a recipe (and not just a raw supply), add to result
            // Note: We can check if it was in the original recipes list, 
            // or simply rely on the flow since supplies are not recipes.
            // However, the problem asks for recipes specifically.
            // A simple check is if it's in our in_degree map.
            if (in_degree.find(current) != in_degree.end()) {
                result.push_back(current);
            }

            // Unlock neighbors
            if (graph.find(current) != graph.end()) {
                for (const string& neighbor : graph[current]) {
                    in_degree[neighbor]--;
                    if (in_degree[neighbor] == 0) {
                        q.push(neighbor);
                    }
                }
            }
        }

        return result;
    }
};

Java Solution for LeetCode 2115

java
import java.util.*;

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        // Graph: ingredient -> list of recipes dependent on it
        Map<String, List<String>> graph = new HashMap<>();
        // In-degree: recipe -> number of ingredients needed
        Map<String, Integer> inDegree = new HashMap<>();
        
        // Initialize in-degree for all recipes
        for (String recipe : recipes) {
            inDegree.put(recipe, 0);
        }
        
        // Build graph and calculate in-degrees
        for (int i = 0; i < recipes.length; i++) {
            String recipe = recipes[i];
            List<String> neededIngredients = ingredients.get(i);
            
            for (String ingredient : neededIngredients) {
                graph.putIfAbsent(ingredient, new ArrayList<>());
                graph.get(ingredient).add(recipe);
                inDegree.put(recipe, inDegree.get(recipe) + 1);
            }
        }
        
        // Queue for BFS, initialized with supplies
        Queue<String> queue = new LinkedList<>();
        for (String supply : supplies) {
            queue.offer(supply);
        }
        
        List<String> result = new ArrayList<>();
        
        while (!queue.isEmpty()) {
            String current = queue.poll();
            
            // If the graph contains dependencies for this item
            if (graph.containsKey(current)) {
                for (String neighbor : graph.get(current)) {
                    inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                    
                    if (inDegree.get(neighbor) == 0) {
                        queue.offer(neighbor);
                        result.add(neighbor);
                    }
                }
            }
        }
        
        return result;
    }
}

Python Solution for LeetCode 2115

python
from collections import deque, defaultdict
from typing import List

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        # Graph: ingredient -> list of recipes that need it
        graph = defaultdict(list)
        # In-degree: recipe -> count of missing ingredients
        in_degree = {recipe: 0 for recipe in recipes}
        
        # Build graph
        for recipe, ing_list in zip(recipes, ingredients):
            for ing in ing_list:
                graph[ing].append(recipe)
                in_degree[recipe] += 1
        
        # Initialize queue with supplies
        queue = deque(supplies)
        result = []
        
        while queue:
            current = queue.popleft()
            
            # If current item unlocks any recipes
            if current in graph:
                for neighbor in graph[current]:
                    in_degree[neighbor] -= 1
                    if in_degree[neighbor] == 0:
                        queue.append(neighbor)
                        result.append(neighbor)
                        
        return result

• The adjacency list stores dependencies, taking $O(E)$ space.
• The in-degree map and queue store nodes, taking $O(V)$ space.