Find All Possible Recipes from Given Supplies
Understanding the Problem
We're given a set of recipes, each with a list of required ingredients. Some ingredients come from our initial supplies, but others might themselves be recipes that we need to create first. The question is: which recipes can we ultimately make?
The complication is the dependency chain. Recipe A might need Recipe B as an ingredient, and Recipe B might need Recipe C. We can only make A if we can first make B, which requires first making C. This is not a simple lookup problem. We need to determine which recipes are achievable once dependencies are resolved.
This is a dependency resolution problem, the same shape that package managers (npm, pip, maven) solve: some packages depend on others, and the system figures out which ones can be installed and in what order. We can model it as a graph, where recipes depend on their ingredients, and find which recipes have all their dependencies satisfiable.
One detail decides correctness: an ingredient counts as available only if it is a supply or a recipe we can also make. An ingredient that is neither a supply nor a listed recipe can never be obtained, so any recipe needing it fails. Circular dependencies (A needs B, B needs A) also fail, since neither can ever be resolved first.
Key Constraints:
1 <= n <= 100→ With at most 100 recipes, an O(n^2) round-based scan is fast enough, though a linear-time graph traversal is cleaner.1 <= ingredients[i].length, supplies.length <= 100→ The dependency graph holds at most 100 * 100 = 10,000 edges, small enough to build and traverse fully.- Strings are at most 10 lowercase letters, so hash-set lookups by ingredient name are effectively constant time.
Approach 1: Brute Force (Iterative Resolution)
Intuition
Make recipes in rounds. In each round, scan every recipe not yet made and check whether all its ingredients are available now, either from supplies or from recipes made in an earlier round. Each recipe that can be made gets added to the available set. Repeat until a full round produces no new recipes.
The termination argument is straightforward: each round either makes at least one new recipe or makes none. If it makes none, no further round ever can, because the available set has not changed, so we stop. Since there are at most n recipes to make, the loop runs at most n + 1 rounds.
Algorithm
- Add all supplies to a set of available items.
- Create a boolean array to track which recipes we've already made.
- Repeat:
- For each unmade recipe, check if all its ingredients are in the available set.
- If yes, add the recipe to the available set and mark it as made.
- If no new recipe was made in this round, stop.
- Return all recipes that were successfully made.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2 * m). In the worst case, each round resolves exactly one recipe, so we run n rounds. Each round scans all n recipes and checks up to m ingredients per recipe.
- Space Complexity: O(n + s). The available set holds up to n recipes plus s supplies. The made array uses O(n) space.
This rescans every unmade recipe each round, including ones whose dependencies are nowhere close to ready. The next approach tracks dependencies explicitly and touches a recipe only when one of its ingredients becomes available.
Approach 2: Topological Sort (BFS / Kahn's Algorithm)
Intuition
Treat this as a dependency graph and run a topological sort. Each recipe depends on its ingredients. Some ingredients are supplies with no dependencies of their own, and some are other recipes. We process items in an order where dependencies come first.
For each recipe, count the number of ingredients it needs and call that its in-degree: the number of ingredients it is still waiting on. Put all supplies into a queue. When an item comes off the queue, it is available, so decrement the in-degree of every recipe that lists it. When a recipe's in-degree reaches zero, all its ingredients are available, so we make it and enqueue it (now it can satisfy other recipes that depend on it).
A recipe in a cycle never reaches in-degree zero. If A needs B and B needs A, each waits on the other, so neither is ever enqueued and neither appears in the result.
Algorithm
- Build a graph: for each recipe, for each of its ingredients, create an edge from the ingredient to the recipe.
- For each recipe, compute its in-degree: the total number of ingredients it requires.
- Initialize a queue with all supplies.
- While the queue is not empty:
- Dequeue an item.
- For each recipe that depends on this item, decrement its in-degree.
- If a recipe's in-degree reaches 0, add it to the queue and to the result.
- Return the result.
Visualization and Code
Loading animation...
- Time Complexity: O(n m + s). Building the graph takes O(n m) where n is the number of recipes and m is the average ingredient count. BFS processes each supply and recipe at most once.
- Space Complexity: O(n m + s). The graph stores at most n m edges. The in-degree map stores n entries. The queue holds at most n + s items.
BFS builds the graph upfront and resolves recipes bottom-up. The next approach goes top-down: starting from each recipe, it recurses only into the dependencies that recipe needs and caches each answer.
Approach 3: DFS with Memoization
Intuition
Instead of resolving bottom-up like topological sort, work top-down. For each recipe, ask whether it can be made by recursively checking its ingredients. An ingredient is available if it is a supply, or if it is itself a recipe that can be made.
Memoization keeps this linear. Once a recipe is resolved as makeable or not, that result is cached so the recursion never recomputes it. Cycle detection needs care: if checking Recipe A leads the recursion back into A before A is resolved, that is a circular dependency, and A cannot be made.
Each recipe carries one of three states: unvisited, visiting (currently on the recursion stack, the marker that detects cycles), and resolved (makeable or not). The visiting state is what distinguishes a cycle from a normal cache hit. Reaching a node still marked visiting means we are partway through resolving it and have looped back to it, so it depends on itself.
Algorithm
- Add all supplies to a set of available items.
- Create a map from recipe name to its ingredient list (for quick lookup).
- For each recipe, call a DFS function that returns whether the recipe can be made.
- In the DFS function:
- If the item is a supply, return true.
- If the item is not a recipe, return false (it's an unknown ingredient).
- If the recipe is currently being visited (cycle), return false.
- If the recipe has already been resolved, return the cached result.
- Mark the recipe as "visiting."
- Recursively check all ingredients. If any returns false, mark this recipe as "cannot make."
- If all ingredients return true, mark this recipe as "can make."
- Collect all recipes marked as "can make."
Visualization and Code
Loading animation...
- Time Complexity: O(n * m). Each recipe is visited at most once due to memoization. For each recipe, we check all its ingredients. Total work is proportional to the total number of ingredient entries.
- Space Complexity: O(n * m). The recipe map stores all ingredient lists. The state map and recursion stack use O(n) space. Recursion depth is at most n.