2115: Find-All-Possible-Recipes-from-Given-Supplies
Medium

I am trying to cook by finding all the possible recipes from the given supplies.

I decided to pursue a depth-first search solution. From a high-level perspective, whenever we check the ingredients inside of a recipe, if we were to stumble upon an unknown recipe inside of the ingredients, it makes sense to check if the unknown recipe is feasible before moving onto the next ingredient.

That is basically a high-level description of DFS; whenever we see a node, we want to check its children before moving on.

I guess you also need to check for loops inside of the graph when running DFS; however, such a problem can be easily nullified with the addition of a seen array.

Code:

class Solution {
public:
    vector<string> ans = {};
    // recursive function that checks if this recipe is cookable
    // - calls itself on children that are unseen recipes
    bool cookable(int food_index, vector<int> &seen, vector<vector<string>>& ingredients, vector<string>& recipes, unordered_map<string, int> &current_supplies) {
        if (seen[food_index] == 2) return false;
        else if (seen[food_index] == 1) return true;

        seen[food_index] = 2; 
        for (int i = 0; i < ingredients[food_index].size(); ++i) {
            string ingredient = ingredients[food_index][i];
            int supply_index = current_supplies[ingredient];
            if (supply_index == 0) {
                return false;
            } else if (supply_index > 0) {
                if (seen[supply_index-1] == 2) {
                    return false;
                } else if (seen[supply_index-1] == 0) {
                    if (cookable(supply_index-1, seen, ingredients, recipes, current_supplies)) {
                        seen[supply_index-1] = 1;
                        ans.push_back(recipes[supply_index-1]);
                    } else {
                        return false;
                    }
                } 
            }
        }
        return true;
    }
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        // basically `current_supplies` stores all the supplies and ingredients
        // - if current_supplies[food] == -1, then it is in `supplies`
        // - if current_supplies[food] > 1, then it stores the index of the recipe in `recipes` (the index is `current_supplies[food]-1`)
        // - if current_supplies[food] == 0, then it does not exist
        unordered_map<string, int> current_supplies;
        for (int i = 0; i < recipes.size(); ++i) {
            current_supplies[recipes[i]] = i+1;
        }
        for (string supply : supplies) {
            current_supplies[supply] = -1;
        }
        
        int ans_size = -1;
        // stores `seen` recipes
        // - if `seen[index] == 1`, then it is a valid recipe
        // - if `seen[index] == 2`, then it is an invalid recipe
        vector<int> seen (recipes.size(), 0);

        for (int i = 0; i < recipes.size(); ++i) {
            if (seen[i] != 0) continue;
            // check if this recipe is 'cookable' or not
            if (cookable(i, seen, ingredients, recipes, current_supplies)) {
                seen[i] = 1;
                ans.push_back(recipes[i]);
            }
        }
        return ans;
    }
};

Complexity: