2115. Find All Possible Recipes from Given Supplies

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.

class Solution {
    set<string> v;
    bool canMake(unordered_map<string, int>& r, vector<vector<string>>& i, unordered_set<string>& s, unordered_set<string>& res, string target) {
        if(s.count(target)) return true;
        if(!r.count(target) or v.count(target)) return false;
        v.insert(target);

        bool make(true), tmp;
        for(auto& ing: i[r[target]]) {
            make &= tmp = canMake(r, i, s, res, ing);
            if(tmp) s.insert(ing);
        }

        if(make) res.insert(target), s.insert(target);
        return make;
    }
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_set<string> s(supplies.begin(), supplies.end()), res;
        unordered_map<string, int> r;
        for(int i = 0; i < recipes.size(); ++i) r[recipes[i]] = i;

        for(auto& _r: r) {
            canMake(r, ingredients, s, res, _r.first);
        }

        return vector<string>(res.begin(), res.end());
    }
};