<p>You have information about <code>n</code> different recipes. You are given a string array <code>recipes</code> and a 2D string array <code>ingredients</code>. The <code>i<sup>th</sup></code> recipe has the name <code>recipes[i]</code>, and you can <strong>create</strong> it if you have <strong>all</strong> the needed ingredients from <code>ingredients[i]</code>. Ingredients to a recipe may need to be created from <strong>other </strong>recipes, i.e., <code>ingredients[i]</code> may contain a string that is in <code>recipes</code>.</p>

<p>You are also given a string array <code>supplies</code> containing all the ingredients that you initially have, and you have an infinite supply of all of them.</p>

<p>Return <em>a list of all the recipes that you can create. </em>You may return the answer in <strong>any order</strong>.</p>

<p>Note that two recipes may contain each other in their ingredients.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> recipes = [&quot;bread&quot;], ingredients = [[&quot;yeast&quot;,&quot;flour&quot;]], supplies = [&quot;yeast&quot;,&quot;flour&quot;,&quot;corn&quot;]
<strong>Output:</strong> [&quot;bread&quot;]
<strong>Explanation:</strong>
We can create &quot;bread&quot; since we have the ingredients &quot;yeast&quot; and &quot;flour&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> recipes = [&quot;bread&quot;,&quot;sandwich&quot;], ingredients = [[&quot;yeast&quot;,&quot;flour&quot;],[&quot;bread&quot;,&quot;meat&quot;]], supplies = [&quot;yeast&quot;,&quot;flour&quot;,&quot;meat&quot;]
<strong>Output:</strong> [&quot;bread&quot;,&quot;sandwich&quot;]
<strong>Explanation:</strong>
We can create &quot;bread&quot; since we have the ingredients &quot;yeast&quot; and &quot;flour&quot;.
We can create &quot;sandwich&quot; since we have the ingredient &quot;meat&quot; and can create the ingredient &quot;bread&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> recipes = [&quot;bread&quot;,&quot;sandwich&quot;,&quot;burger&quot;], ingredients = [[&quot;yeast&quot;,&quot;flour&quot;],[&quot;bread&quot;,&quot;meat&quot;],[&quot;sandwich&quot;,&quot;meat&quot;,&quot;bread&quot;]], supplies = [&quot;yeast&quot;,&quot;flour&quot;,&quot;meat&quot;]
<strong>Output:</strong> [&quot;bread&quot;,&quot;sandwich&quot;,&quot;burger&quot;]
<strong>Explanation:</strong>
We can create &quot;bread&quot; since we have the ingredients &quot;yeast&quot; and &quot;flour&quot;.
We can create &quot;sandwich&quot; since we have the ingredient &quot;meat&quot; and can create the ingredient &quot;bread&quot;.
We can create &quot;burger&quot; since we have the ingredient &quot;meat&quot; and can create the ingredients &quot;bread&quot; and &quot;sandwich&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == recipes.length == ingredients.length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= ingredients[i].length, supplies.length &lt;= 100</code></li>
	<li><code>1 &lt;= recipes[i].length, ingredients[i][j].length, supplies[k].length &lt;= 10</code></li>
	<li><code>recipes[i], ingredients[i][j]</code>, and <code>supplies[k]</code> consist only of lowercase English letters.</li>
	<li>All the values of <code>recipes</code> and <code>supplies</code>&nbsp;combined are unique.</li>
	<li>Each <code>ingredients[i]</code> does not contain any duplicate values.</li>
</ul>

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        """
        recipe: 1D array of strings, we need all the ingredients in ingredients[i] to make recipe[i]
        ingredients: 2D array of strings, ingredients[i]
        supplies: 1D array of strings, the ingredients we initially have, infinite supply of them

        return a list of all the recipes you can create, 1D array of strings, in any order
        * ingredients from a recipe can be created from other recipes, ingredients[i] can contain a string that is in recipes
        * we need to keep track of the relationship between a recipe and its ingredients

        can ingredients contain any duplicate values?
        can recipes contain any duplicate values?
        are we guaranteed valid input?
        are values in recipes and supplies unique?
        are the supplies just the raw ingredients or can it contain recipes created from raw ingredients?

        # SET: supplies can be kept in a set -- we can easily check if we have a specific raw ingredient
        # SET: recipes that we've seen and know that we can make can be kept in another set -- we can easily check if we can make this recipe
        # DICTIONARY: key - recipe, value - ingredients (set) -- we can use it to easily get the ingredients needed for a recipe and we can use that to check if we have all the supplies
        
        turn supplies into a supplies_set
        initialize a recipes_can_make set
        recipes_to_ingredients = {}
        for i in recipes and ingredients
            recipes_to_ingredients[recipes[i]] = set(ingredients[i])

        def recursion(recipe):
            # we know the recipe is in the recipe dictionary
            if recipe not in ingredients and recipe not in recipes_to_ingredients:
                return False
            if recipe in recipes_to_ingredients:
                return True
            if ingredients not in supplies and in recipes dictionary:
                    if recipe isn't in recipes_can_make_set:
                        do a recursion on this recipe
                        if recursion returns False:
                            can_make = False
                            break
            for 

        for recipe in recipes_to_ingredients:
            can_make = True
            we can loop through the ingredients
                if not can_make_recipe():
                    can_make = False
                    break
            if can_make:
                output.append(recipe)
        """

        supplies_set = set(supplies)
        verified_recipes = set()
        recipes_to_ingredients = {}
        for i in range(len(recipes)):
            recipes_to_ingredients[recipes[i]] = ingredients[i]

        def can_make_recipe(ingredient, seen):
            if ingredient in seen:
                return False
            # if we already have the supplies for ingredient return true
            if ingredient in supplies_set:
                return True
            # if we don't have the supplies and ingredient isn't also a recipe, return False
            if ingredient not in recipes_to_ingredients:
                return False
            # otherwise we know the ingredient at least exists in the recipes so we see if we can make this recipe based on its ingredients

            # if we've already processed this recipe / ingredient, and we know we can make it, return True
            if ingredient in verified_recipes:
                return True

            seen.add(ingredient)
            for ing in recipes_to_ingredients[ingredient]:
                can_make = True
                if not can_make_recipe(ing, seen):
                    can_make = False
                    break
            if can_make:
                verified_recipes.add(ingredient)
                return True
            return False

        output = []
        for recipe in recipes_to_ingredients:
            can_make = True
            for ingredient in recipes_to_ingredients[recipe]:
                seen = set()
                if not can_make_recipe(ingredient, seen):
                    can_make = False
                    break
            if can_make:
                verified_recipes.add(recipe)
                output.append(recipe)
        
        return output
25600