Problem Informations

• Problem Index: 2115
• Problem Link: Find All Possible Recipes from Given Supplies
• Topics: Array, Hash Table, String, Graph, Topological Sort

Problem Description

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.

Example 1:

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

Example 2:

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

Example 3:

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 \leq n \leq 100$
• $1 \leq ingredients[i].length, supplies.length \leq 100$
• $1 \leq recipes[i].length, ingredients[i][j].length, supplies[k].length \leq 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.

Intuition

The problem at hand requires determining which recipes can be created given a list of recipes, their required ingredients, and an initial set of supplies. Some recipes can act as ingredients for other recipes, creating a dependency chain. Thus, the problem can be viewed as a graph traversal where nodes are recipes and edges represent ingredient dependencies. The key challenge is to ensure that all dependencies for a recipe are satisfied either directly through the initial supplies or indirectly via other creatable recipes.

Approach

The solution employs a dynamic programming approach alongside graph traversal techniques to efficiently determine which recipes can be created. The overall strategy involves the following steps:

1. Data Structure Initialization:

   • Use a set to maintain the availableSupplies, which includes all initially available ingredients.
   • Use a map (recipeIndexMap) to associate each recipe with its index for quick lookup.
   • Use a vector (dp) for memoization to store computation results for each recipe. Each entry in dp can be -1 (unvisited), 0 (cannot make the recipe), or 1 (can make the recipe).

2. Mapping Recipes to Indices:

   • Iterate over all recipes and populate recipeIndexMap to easily fetch the index of a recipe in the recipes list.

3. Checking Creatable Recipes Using DFS with Memoization:

   • For each recipe, invoke a helper function canMakeRecipe() to check if the recipe can be created.
   • In canMakeRecipe(), use memoization to avoid recalculating results for recipes that have already been checked.
   • For each ingredient required by the recipe:
     • If the ingredient is not available in availableSupplies and is not a creatable recipe according to prior calculations, mark the recipe as not creatable (dp[index] = 0) and return false.
   • If all ingredients of a recipe are satisfied, mark it as creatable (dp[index] = 1) and return true.

4. Gathering Creatable Recipes:

   • Iterate over the recipes list and, for each recipe, use the result from canMakeRecipe() to determine if it can be added to the creatableRecipes list.

By following this approach, the algorithm ensures each recipe is processed efficiently, incorporating direct supplies and possible recursive dependencies through other recipes. This method effectively solves the problem by dynamically determining the creatable recipes based on the given ingredients and supplies constraints.

Code

C++

class Solution {
public:
    // Helper function to determine if a recipe can be created
    bool canMakeRecipe(
        int index, 
        vector<string>& recipes, 
        vector<vector<string>>& ingredients, 
        set<string>& availableSupplies, 
        vector<int>& dp, 
        map<string, int>& recipeIndexMap
    ) {
        // Memoization to check if the result is previously computed
        if (dp[index] != -1) 
            return dp[index];

        // Initialize with failure state
        dp[index] = 0;

        // Check if all ingredients are available or can be created
        for (string ingredient : ingredients[index]) {
            // If ingredient is not a supply and not a creatable recipe
            if (availableSupplies.count(ingredient) == 0 && 
                (recipeIndexMap.find(ingredient) == recipeIndexMap.end() || 
                 !canMakeRecipe(recipeIndexMap[ingredient], recipes, ingredients, availableSupplies, dp, recipeIndexMap))) 
                return dp[index] = 0; // Cannot create the recipe
        }

        // All ingredients are available, recipe can be created
        return dp[index] = 1;
    }

    // Main function to find all creatable recipes
    vector<string> findAllRecipes(
        vector<string>& recipes, 
        vector<vector<string>>& ingredients, 
        vector<string>& supplies
    ) {
        set<string> availableSupplies(supplies.begin(), supplies.end()); // Set of initial available supplies
        map<string, int> recipeIndexMap; // Maps recipe name to its index
        vector<string> creatableRecipes; // List to store creatable recipes
        vector<int> dp(recipes.size(), -1); // Memoization vector (-1: unvisited, 0: cannot make, 1: can make)

        // Map each recipe to its corresponding index
        for (int i = 0; i < recipes.size(); i++)
            recipeIndexMap[recipes[i]] = i;

        // Check each recipe if it can be created
        for (int i = 0; i < recipes.size(); i++) {
            if (canMakeRecipe(i, recipes, ingredients, availableSupplies, dp, recipeIndexMap))
                creatableRecipes.push_back(recipes[i]);
        }

        return creatableRecipes; // Return all recipes that can be created
    }
};

Python

class Solution:
    # Helper function to determine if a recipe can be created
    def canMakeRecipe(
        self, 
        index, 
        recipes, 
        ingredients, 
        availableSupplies, 
        dp, 
        recipeIndexMap
    ):
        # Memoization to check if the result is previously computed
        if dp[index] != -1:
            return dp[index]

        # Initialize with failure state
        dp[index] = 0

        # Check if all ingredients are available or can be created
        for ingredient in ingredients[index]:
            # If ingredient is not a supply and not a creatable recipe
            if (ingredient not in availableSupplies and 
                (ingredient not in recipeIndexMap or 
                 not self.canMakeRecipe(recipeIndexMap[ingredient], recipes, ingredients, availableSupplies, dp, recipeIndexMap))):
                return dp[index]  # Cannot create the recipe

        # All ingredients are available, recipe can be created
        dp[index] = 1
        return dp[index]

    # Main function to find all creatable recipes
    def findAllRecipes(self, recipes, ingredients, supplies):
        availableSupplies = set(supplies)  # Set of initial available supplies
        recipeIndexMap = {}  # Maps recipe name to its index
        creatableRecipes = []  # List to store creatable recipes
        dp = [-1] * len(recipes)  # Memoization vector (-1: unvisited, 0: cannot make, 1: can make)

        # Map each recipe to its corresponding index
        for i in range(len(recipes)):
            recipeIndexMap[recipes[i]] = i

        # Check each recipe if it can be created
        for i in range(len(recipes)):
            if self.canMakeRecipe(i, recipes, ingredients, availableSupplies, dp, recipeIndexMap):
                creatableRecipes.append(recipes[i])

        return creatableRecipes  # Return all recipes that can be created

Complexity

• Time complexity: The time complexity is $O(|R| \cdot |I|)$, where $|R|$ is the number of recipes, and $|I|$ is the maximum number of ingredients in a recipe. The canMakeRecipe function works by iterating over the ingredients of each recipe, and during the recursion, it checks for creatable ingredients recursively as well. This forms a DFS (Depth First Search) over the recipe graph. Since each call of canMakeRecipe is memoized, each recipe is examined a limited number of times in terms of its direct and transitive dependencies, leading to a linear relationship with respect to recipes and ingredients. Iterating for all recipes further multiplies this by the number of recipes.

• Space complexity: The space complexity is $O(|R| + |S|)$, where $|R|$ is the number of recipes and $|S|$ is the number of initial supplies. This accounts for storing the available supplies in a set and the memoization status of dp array. Each map and set used in the function requires space proportional to the number of stored elements, namely the recipes and supplies. The recursive call stack could also contribute to space usage, but this is bounded by these primary storage structures.