> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find All Possible Recipes from Given Supplies

> Tested Python solution for LeetCode 2115 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 2115, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Graph Theory](/catalog/topics/graph-theory), [Topological Sort](/catalog/topics/topological-sort), Directed Acyclic Graph. [View on LeetCode](https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2115   # by problem number
lcpy gen -s find_all_possible_recipes_from_given_supplies   # by problem name
```

## Problem

You have information about `n` different recipes. You are given a string array `recipes` and a 2D string array `ingredients`. The `i`th 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.

### Examples

```
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".
```

```
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".
```

```
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.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_all_possible_recipes_from_given_supplies/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_all_possible_recipes_from_given_supplies/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(V + E) over recipes and ingredient references
    # Space: O(V + E)
    def find_all_recipes(
        self, recipes: list[str], ingredients: list[list[str]], supplies: list[str]
    ) -> list[str]:
        recipe_set = set(recipes)
        remaining = {r: len(ings) for r, ings in zip(recipes, ingredients, strict=True)}
        dependents: dict[str, list[str]] = {}
        for recipe, ings in zip(recipes, ingredients, strict=True):
            for ing in ings:
                dependents.setdefault(ing, []).append(recipe)
        made: list[str] = []
        queue: deque[str] = deque(supplies)
        queue.extend(recipe for recipe in recipes if remaining[recipe] == 0)
        while queue:
            item = queue.popleft()
            if item in recipe_set:
                made.append(item)
            for recipe in dependents.get(item, ()):
                remaining[recipe] -= 1
                if remaining[recipe] == 0:
                    queue.append(recipe)
        return made
```

## Complexity

| Time | Space |
| - | - |
| O(V + E) over recipes and ingredient references | O(V + E) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.