You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from 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.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 letters.recipes and supplies combined are unique.ingredients[i] does not contain any duplicate values.This approach uses graph theory to solve the problem. Each recipe and ingredient is considered a node. An edge from node A to node B indicates that node B is needed to create node A. We can then perform a topological sort utilizing Kahn's Algorithm to determine the order in which we can create the recipes.
In this implementation, we first build the graph and compute the in-degrees of each recipe. We fill the queue with our initial supplies and perform a BFS. We decrement the in-degree of the neighboring nodes when visiting each node, and if a neighbor's in-degree becomes zero, it means that all ingredients to make it are available, so we add it to the queue.
C++
Time Complexity: O(n + m), where n is the number of recipes and m is the total number of ingredients.
Space Complexity: O(n + m), due to the graph and in-degree storage.
This approach involves trying to create each recipe by checking if all its ingredients are available or can be created from other recipes. We use memoization to store the results of subproblems, avoiding redundant calculations.
This implementation checks each recipe to see if it can be created using a recursive backtracking approach. It covers all subproblems using memoization, thereby improving efficiency. An ingredient is considered ready if it can be created from available supplies, its own recipe, or if it already appears in supplies.
C#
Time Complexity: O(n * m), where n is the number of recipes and m is the average number of ingredients.
Space Complexity: O(n + m), due to the auxiliary data structures used for memoization and recursion stack.
| Approach | Complexity |
|---|---|
| Topological Sort using Kahn's Algorithm | Time Complexity: O(n + m), where n is the number of recipes and m is the total number of ingredients. |
| Backtracking with Memoization | Time Complexity: O(n * m), where n is the number of recipes and m is the average number of ingredients. |
Find All Possible Recipes from Given Supplies - Leetcode 2115 - Python • NeetCodeIO • 9,541 views views
Watch 9 more video solutions →Practice Find All Possible Recipes from Given Supplies with our built-in code editor and test cases.
Practice on FleetCode