← DSA Atlas
Dedicated problem page · #2115

Find All Possible Recipes from Given Supplies

MediumTopological SortDependency resolution via topological orderKahn's BFS topological sort
Solve on LeetCode ↗
2115
MediumTopological SortKahn's BFS topological sortDependency resolution via topological order

Find All Possible Recipes from Given Supplies

You have n recipes: recipes[i] can be made only if you have every item in ingredients[i]. An ingredient may itself be another recipe. You also have an array supplies of items you own in unlimited quantity. Return all recipes you can create, in any order.

Open official problem prompt ↗
In plain English

Determine which recipes are actually buildable given a starting pantry, accounting for recipes that serve as ingredients to other recipes.

Picture it like this

Like a crafting tech tree in a game: you start with raw resources, craft an intermediate item, and that intermediate unlocks the next tier. You keep crafting whatever has all its inputs satisfied until nothing new can be made.

Example
Input
recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output
["bread","sandwich"]
Why
Bread is made from the supplies yeast and flour; once bread exists it plus the supply meat makes 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 lettersAll the values of recipes and supplies combined are uniqueEach ingredients[i] does not contain any duplicate values
Pattern lesson

See the pattern, then code

Dependency resolution via topological order
Recognition clue

Items that unlock other items, where making one recipe can satisfy another's ingredient, is a dependency graph — resolve it in topological order starting from what you already have.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. Give each recipe an indegree equal to its number of ingredients. Start from the supplies you own; every time an item becomes available, decrement the indegree of recipes that need it. A recipe whose indegree hits zero is fully satisfied, becomes makeable, and can in turn unlock further recipes.

New words, made simpleKnow these before the algorithm
Supply
A base item you own in unlimited quantity; always available from the start.
Indegree
The count of a recipe's ingredients not yet available.
Unlock
Making a recipe, which then counts as an available ingredient for others.
Frontier queue
The set of currently available items whose downstream recipes still need checking.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Repeated full scans until no change

Correct but wasteful: it rescans every recipe on each round even when nothing about it changed.

Loop over all recipes repeatedly, marking any whose ingredients are all available, until a full pass makes no new recipe.

Time O(N^2 * M)Space O(N)
Best choiceKahn's topological sort

Each ingredient edge is processed exactly once, giving a clean linear resolution.

Track each recipe's unmet-ingredient count and only touch a recipe when one of its ingredients becomes available.

Time O(N + E)Space O(N + E)
The rule we keep true

Invariant

A recipe is added to the result only when its indegree reaches zero, which happens exactly when every one of its ingredients has become available (from supplies or from a previously made recipe).

Why this is correct

Reasoning

The queue always holds items known to be available. Consuming an item decrements exactly the recipes that listed it, so a recipe's indegree reaching zero certifies all its ingredients are present. Because a newly made recipe is itself enqueued, chained dependencies resolve in order, and every ingredient-to-recipe edge is examined once, so no makeable recipe is missed and none is claimed prematurely.

The algorithm in three movesSay these aloud before coding
1Set each recipe's indegree to its ingredient count

indeg = {bread:2, sandwich:2}

2Map every ingredient to the list of recipes that require it

yeast,flour consumed -> bread ready

3Seed a queue with all supplies (items you already own)

bread,meat consumed -> sandwich ready

4Pop an item, decrement indegree of each recipe needing it; when a recipe reaches zero, add it to the result and enqueue it

5Return the collected recipes

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
yeast0
flour1
meat2
bread3
sandwich4
1 · Readrecipes/ingredients
2 · AskHow many ingredients does each recipe need?
3 · Update stateindeg = {bread:2, sandwich:2}; need = {yeast:[bread], flour:[bread], bread:[sandwich], meat:[sandwich]}
4 · ResultQueue seeded with supplies [yeast, flour, meat]
Key takeaway

Supplies yeast/flour/meat (highlighted) cascade to unlock bread, which then unlocks sandwich.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-9Build indegrees and reverse edges

    Each recipe's indegree is its ingredient count; need maps an ingredient to every recipe that depends on it.

  2. 2
    Lines 10-11Seed with what you own

    All supplies go into the frontier queue as guaranteed-available items.

  3. 3
    Lines 12-18Cascade availability

    Consuming an available item lowers the indegree of dependent recipes; one that reaches zero is made, recorded, and enqueued so it can unlock further recipes.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A recipe needing an ingredient that is neither a supply nor any other recipe: its indegree never reaches zero, so it is correctly excluded
  • Cyclic dependencies (recipe A needs B and B needs A): neither ever reaches indegree zero, so both are excluded
  • A recipe whose ingredients are all base supplies: made immediately
  • Chains where recipe C depends on B depends on A: resolved in cascade order
!

Common beginner mistakes

  • Treating recipes and supplies as disjoint and forgetting a recipe can be another recipe's ingredient — the enqueue of finished recipes is what handles this
  • Checking availability with a static set of supplies only, missing recipes unlocked mid-process
  • Assuming ingredient order or that all recipes are eventually makeable; unmakeable ones must be silently dropped
  • Double-counting duplicate ingredients — constraints guarantee no duplicates within a recipe, so indegree equals the raw ingredient count
Check your understanding

How does this algorithm naturally exclude recipes stuck in a dependency cycle or missing a base ingredient?

More in Topological Sort

#207Course ScheduleCycle detection by peeling zero in-degree nodes#210Course Schedule IIEmit nodes in dependency-safe order#269Alien DictionaryDerive edges from adjacent-item comparisons, then topologically sort#310Minimum Height TreesTrim leaves inward until the center remains#329Longest Increasing Path in a MatrixLongest path in an implicit DAG via memoized DFS#1203Sort Items by Groups Respecting DependenciesTwo-level topological sort (order groups, then items within groups)