# Find All Possible Recipes from Given Supplies
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies)
Canonical: https://scaleengineer.com/dsa/problems/find-all-possible-recipes-from-given-supplies
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Hash Table, String, Graph
**Companies:** [TikTok](https://scaleengineer.com/companies/tiktok), [PhonePe](https://scaleengineer.com/companies/phonepe), [Verily](https://scaleengineer.com/companies/verily)
---
## Problem
You have information about `n` different recipes. You are given a string array `recipes` and a 2D string array `ingredients`. The `ith` recipe has the name `recipes[i]`, and you can **create** it if you have **all** the needed ingredients from `ingredients[i]`. A recipe can also be an ingredient for **other** recipes, i.e., `ingredients[i]` may contain a string that is in `recipes`.

You are also given a string array `supplies` containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return _a list of all the recipes that you can create._ You may return the answer in **any order**.

Note that two recipes may contain each other in their ingredients.

**Example 1:**

**Input:** recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
**Output:** ["bread"]
**Explanation:**
We can create "bread" since we have the ingredients "yeast" and "flour".

**Example 2:**

**Input:** recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
**Output:** ["bread","sandwich"]
**Explanation:**
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

**Example 3:**

**Input:** recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
**Output:** ["bread","sandwich","burger"]
**Explanation:**
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

**Constraints:**

* `n == recipes.length == ingredients.length`
* `1 <= n <= 100`
* `1 <= ingredients[i].length, supplies.length <= 100`
* `1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10`
* `recipes[i], ingredients[i][j]`, and `supplies[k]` consist only of lowercase English letters.
* All the values of `recipes` and `supplies` combined are unique.
* Each `ingredients[i]` does not contain any duplicate values.

# Approaches
## Brute-force Simulation
This approach simulates the process of cooking recipes iteratively. We start with the initial supplies and in each round, we try to create new recipes with the ingredients we currently have. We repeat this process until no new recipes can be created in a full round.
**Time:** O(N^2 * M * K), where N is the number of recipes, M is the maximum number of ingredients for a recipe, and K is the maximum length of a string. The outer `while` loop can run at most N times (as we create at least one recipe per successful iteration). Inside, we loop through N recipes. For each recipe, we check up to M ingredients. Set lookups take O(K) on average for hashing the string. · **Space:** O((S + N) * K), where S is the number of supplies, N is the number of recipes, and K is the maximum string length. This is for storing the `available` set, which can hold up to S initial supplies and N created recipes. The result list also contributes O(N * K) space.
**Pros:** Simple to understand and implement.; Doesn't require knowledge of complex data structures or algorithms like graphs.
**Cons:** Inefficient due to repeated scanning of all recipes.; The time complexity is polynomial, which might be too slow for larger constraints.
### Explanation
The core idea is to repeatedly scan all the recipes. We maintain a set of all ingredients we possess, which initially contains just the `supplies`. We then loop through the recipes. If we find a recipe for which we have all the ingredients, we 'create' it. This means we add the recipe itself to our set of available items and to our final answer list. We continue this process, looping over the recipes again and again, because creating one recipe might enable us to create another. The process stops when we complete a full pass through all recipes without being able to create any new ones, indicating that we can't make any further progress.

```java
import java.util.*;

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Set<String> available = new HashSet<>(Arrays.asList(supplies));
        List<String> result = new ArrayList<>();
        int n = recipes.length;
        boolean[] created = new boolean[n];
        
        boolean newRecipeMadeInRound = true;
        // Keep iterating as long as we are creating new recipes
        while (newRecipeMadeInRound) {
            newRecipeMadeInRound = false;
            for (int i = 0; i < n; i++) {
                // Skip recipes that have already been created
                if (created[i]) {
                    continue;
                }
                
                boolean canCreate = true;
                // Check if all ingredients for the current recipe are available
                for (String ingredient : ingredients.get(i)) {
                    if (!available.contains(ingredient)) {
                        canCreate = false;
                        break;
                    }
                }
                
                // If all ingredients are available, create the recipe
                if (canCreate) {
                    result.add(recipes[i]);
                    available.add(recipes[i]);
                    created[i] = true;
                    newRecipeMadeInRound = true;
                }
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize a `Set` of available items with the initial `supplies` for efficient lookup.
- Create a list to store the final creatable recipes.
- Use a `boolean` array to track which recipes have already been created.
- Enter a loop that continues as long as new recipes are being made.
- Inside the loop, iterate through all recipes. For each uncreated recipe, check if all its ingredients are in the `available` set.
- If all ingredients are available, the recipe can be created. Add it to the result list, the `available` set, and mark it as created.
- If a full pass over all recipes results in no new creations, the loop terminates.
- Return the list of created recipes.

## Graph and Topological Sort
This problem can be modeled as a dependency graph, where recipes are nodes and an ingredient requirement forms a directed edge. If recipe R needs ingredient I, there's an edge from I to R. Finding all creatable recipes is equivalent to performing a topological sort on this graph, starting from the initial supplies.
**Time:** O((L + S) * K), where L is the total number of all ingredients for all recipes, S is the number of supplies, and K is the maximum string length. Building the graph takes O(L * K). The topological sort processes each supply and recipe once. The total number of edge traversals is L. Map and queue operations with strings take O(K). This is linear with respect to the size of the input. · **Space:** O((L + S + N) * K), where L is the total number of all ingredients for all recipes, S is the number of supplies, N is the number of recipes, and K is the maximum string length. The adjacency list can store up to L total ingredient dependencies. The in-degree map stores N recipes. The queue can store up to S supplies and N recipes. All keys and values are strings, contributing the K factor.
**Pros:** Highly efficient, with linear time complexity relative to the input size.; Correctly handles complex dependencies and cycles.; It's a standard and robust approach for this category of problems.
**Cons:** More complex to conceptualize and implement compared to the simulation approach.; Requires understanding of graph theory and topological sorting.
### Explanation
A more efficient way to solve this problem is to recognize it as a dependency problem, which is a classic use case for topological sorting. We can think of recipes and ingredients as nodes in a directed graph. An edge from an ingredient `I` to a recipe `R` signifies that `R` depends on `I`.

A recipe can be created only when all its prerequisite ingredients are available. In graph terms, a node can be 'visited' (or a recipe created) only after all its preceding nodes have been visited. This is the exact principle of topological sorting.

We use Kahn's algorithm for topological sorting. We start by building the graph representation: an adjacency list to show which recipes depend on which ingredients, and an in-degree count for each recipe to track how many ingredients are still needed. We initialize a queue with all the initial supplies, as they are the items we have from the start (in-degree 0, conceptually). Then, we process items from the queue. When we process an item (supply or a newly created recipe), we find all recipes that depend on it and reduce their in-degree. If a recipe's in-degree drops to zero, it means all its ingredients are now available, and we can add it to the queue to be processed. Recipes that are part of a cycle (e.g., A needs B, B needs A) will never have their in-degrees drop to zero, so they are correctly excluded.

```java
import java.util.*;

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        // Adjacency list: ingredient -> list of recipes that need it
        Map<String, List<String>> adj = new HashMap<>();
        // In-degree map: recipe -> number of ingredients needed
        Map<String, Integer> inDegree = new HashMap<>();
        // Set of all recipes for quick O(1) average time lookups
        Set<String> recipeSet = new HashSet<>(Arrays.asList(recipes));

        // Build the graph
        for (int i = 0; i < recipes.length; i++) {
            String recipe = recipes[i];
            inDegree.put(recipe, ingredients.get(i).size());
            for (String ingredient : ingredients.get(i)) {
                adj.computeIfAbsent(ingredient, k -> new ArrayList<>()).add(recipe);
            }
        }

        // Queue for topological sort, initialized with available supplies
        Queue<String> queue = new LinkedList<>();
        for (String supply : supplies) {
            queue.offer(supply);
        }

        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            String item = queue.poll();

            // If this item is a recipe that can be made, add to result
            // We only add recipes to the result, not basic supplies
            if (recipeSet.contains(item)) {
                result.add(item);
            }

            // If this item is an ingredient for other recipes, update their in-degrees
            if (adj.containsKey(item)) {
                for (String dependentRecipe : adj.get(item)) {
                    inDegree.put(dependentRecipe, inDegree.get(dependentRecipe) - 1);
                    // If a recipe's in-degree becomes 0, it can now be made
                    if (inDegree.get(dependentRecipe) == 0) {
                        queue.offer(dependentRecipe);
                    }
                }
            }
        }

        return result;
    }
}
```
### Algorithm
- Model the problem as a graph. Create an adjacency list `adj` mapping each ingredient to the list of recipes that require it.
- Create an `inDegree` map to store the number of ingredients required for each recipe.
- Initialize a queue with all the initial `supplies`. These are the starting points of our topological sort, as they have no prerequisites.
- Create a `Set` of all recipe names for quick lookups.
- Process the queue: while it's not empty, dequeue an item.
- If the dequeued item is a recipe, add it to the result list.
- For the dequeued item, find all recipes that depend on it using the `adj` map.
- For each such dependent recipe, decrement its in-degree. If a recipe's in-degree becomes 0, it means all its ingredients are now available, so add it to the queue.
- After the queue is empty, the result list contains all recipes that could be created in a valid order.

# Solutions
### Java

```java
class Solution {
public
  List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients,
                              String[] supplies) {
    Map<String, List<String>> g = new HashMap<>();
    Map<String, Integer> indeg = new HashMap<>();
    for (int i = 0; i < recipes.length; ++i) {
      for (String v : ingredients.get(i)) {
        g.computeIfAbsent(v, k->new ArrayList<>()).add(recipes[i]);
      }
      indeg.put(recipes[i], ingredients.get(i).size());
    }
    Deque<String> q = new ArrayDeque<>();
    for (String s : supplies) {
      q.offer(s);
    }
    List<String> ans = new ArrayList<>();
    while (!q.isEmpty()) {
      for (int n = q.size(); n > 0; --n) {
        String i = q.pollFirst();
        for (String j : g.getOrDefault(i, Collections.emptyList())) {
          indeg.put(j, indeg.get(j) - 1);
          if (indeg.get(j) == 0) {
            ans.add(j);
            q.offer(j);
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> findAllRecipes(vector<string> &recipes,
                                vector<vector<string>> &ingredients,
                                vector<string> &supplies) {
    unordered_map<string, vector<string>> g;
    unordered_map<string, int> indeg;
    for (int i = 0; i < recipes.size(); ++i) {
      for (auto &v : ingredients[i]) {
        g[v].push_back(recipes[i]);
      }
      indeg[recipes[i]] = ingredients[i].size();
    }
    queue<string> q;
    for (auto &s : supplies) {
      q.push(s);
    }
    vector<string> ans;
    while (!q.empty()) {
      for (int n = q.size(); n; --n) {
        auto i = q.front();
        q.pop();
        for (auto j : g[i]) {
          if (--indeg[j] == 0) {
            ans.push_back(j);
            q.push(j);
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]: g = defaultdict(list) indeg = defaultdict(int) for a, b in zip(recipes, ingredients): for v in b: g[v]. append(a) indeg[a] += len(b) q = deque(supplies) ans = [] while q: for _ in range(len(q)): i = q . popleft() for j in g[i]: indeg[j] -= 1 if indeg[j] == 0: ans . append(j) q . append(j) return ans

```