Find All Possible Recipes from Given Supplies - Solution & Explanation

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.