Watch 10 video solutions for Find All Possible Recipes from Given Supplies, a medium level problem involving Array, Hash Table, String. This walkthrough by NeetCodeIO has 12,147 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]. Ingredients to a recipe may need to be created from 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.length1 <= n <= 1001 <= ingredients[i].length, supplies.length <= 1001 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.recipes and supplies combined are unique.ingredients[i] does not contain any duplicate values.Problem Overview: You are given a list of recipes, their required ingredients, and a list of initial supplies. Some ingredients may themselves be recipes. The task is to determine every recipe you can ultimately prepare by resolving these dependencies.
Approach 1: Backtracking with Memoization (DFS) (Time: O(N * K), Space: O(N))
This approach treats the problem as dependency resolution using recursion. For each recipe, run a DFS to check whether all its ingredients can be produced. If an ingredient exists in the supply set, it is immediately usable. If it is another recipe, recursively attempt to build it. Memoization caches whether a recipe is possible or impossible, preventing repeated work across different dependency chains.
The key insight is that recipes form a dependency graph. DFS explores these dependencies until reaching either base supplies or a missing ingredient. Memoization avoids recomputing the same recipe multiple times. This approach works well when the dependency depth is small, but recursive traversal still introduces overhead compared to iterative graph processing.
Relevant concepts include graph traversal and efficient lookups with a hash table.
Approach 2: Topological Sort using Kahn's Algorithm (Time: O(N + E), Space: O(N + E))
This is the optimal approach. Model the problem as a directed graph where ingredients point to recipes that depend on them. Track the number of missing ingredients for each recipe using an indegree counter. All initial supplies are pushed into a queue since they are already available.
Process the queue using Kahn's algorithm. When a supply or completed recipe becomes available, iterate over the recipes that depend on it and decrement their indegree. Once a recipe's indegree reaches zero, every required ingredient is available, so that recipe can be produced and added to the queue as a new supply.
The key insight is that recipes behave like nodes in a dependency DAG. Topological sorting naturally processes them in a valid production order. Each ingredient and dependency edge is processed once, giving linear complexity relative to nodes and edges. This method relies heavily on topological sort and adjacency lists built with arrays and hash maps.
Recommended for interviews: The topological sort solution using Kahn's algorithm is what most interviewers expect. It demonstrates strong understanding of dependency graphs and efficient processing of prerequisites. DFS with memoization still shows solid reasoning and works well conceptually, but the topological approach scales better and is the canonical solution for dependency problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Memoization (DFS) | O(N * K) | O(N) | Useful for understanding dependency resolution or when recursion is easier to implement. |
| Topological Sort (Kahn's Algorithm) | O(N + E) | O(N + E) | Best for large dependency graphs and the expected optimal interview solution. |