Voice Behind codestorywithMIK | Easiest explanation | YouTube
YouTube Video Link : Smallest Sufficient Team\nMy Github Treasure : Smallest Sufficient Team\n\n\n//Approach-1 (Memoize using unordered_map)\nclass Solution {\n
YouTube Video Link : [Smallest Sufficient Team](https://www.youtube.com/watch?v=CAoBD84G2gI)\nMy Github Treasure : [Smallest Sufficient Team](https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Bit%20Magic%20DP/Smallest%20Sufficient%20Team.cpp)\n\n```\n//Approach-1 (Memoize using unordered_map)\nclass Solution {\npublic:\n    \n    int m, n;\n    int target_mask;\n    vector<int> result;\n    unordered_map<string , int > dp;\n    \n    void solve(vector<int> &people_skill , int idx , vector<int> &temp, int mask ) {\n        \n       if(idx == people_skill.size()) {\n           if(mask == target_mask) {\n               if(result.size() == 0 || result.size() >= temp.size()) {\n                   result = temp;\n               }\n           }\n           return;\n       }\n        \n        string s = to_string(idx) + to_string(mask);\n        \n         if(dp.find(s) != dp.end()) {\n           if(dp[s] <= temp.size())\n               return ; \n        }\n        \n        if(result.size() != 0 && temp.size() >= result.size()) \n            return; \n        \n        solve(people_skill , idx + 1 , temp , mask ); // no\n\n         if( (mask | people_skill[idx]) != mask) { //Because a person\'s skill set can be empty. So we won\'t take them\n            temp.push_back(idx);\n            solve(people_skill, idx + 1, temp , mask | people_skill[idx]);\n\n            temp.pop_back();\n            dp[s] = (temp.size() != 0 ) ? temp.size() : -1;\n        }\n    }\n    \n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        n = req_skills.size();                                                                                          \n        m = people.size();\n        \n        unordered_map<string, int> skills; //skill -> unique number\n        for (int i = 0; i < n; ++i)\n            skills[req_skills[i]] = i;\n        \n        // represent each person by a single bitmasked number (k\'th bit represents if a person has the k\'th skill or not)\n        vector<int> people_skill;\n        for (auto &v: people) {\n            int skill_bit = 0;\n            for (string &skill: v)\n                skill_bit |= 1 << skills[skill];\n            \n            people_skill.push_back(skill_bit);\n        }\n        \n        // required set of skills mask (All set to 1s)\n        target_mask = pow(2, n) - 1;\n        vector<int> temp;\n        solve(people_skill, 0, temp, 0);\n        return result;\n    }\n};\n```\n\n```\n//Approach-2 (Using vector<vector<int>> instead of unordered_map to memoize)\n\nclass Solution {\npublic:\n    \n    int m, n;\n    int target_mask;\n    vector<int> result;\n    vector<vector<int>> t;\n    \n    void solve(vector<int> &people , int idx , vector<int> &temp, int mask ) {\n        \n       if(idx == people.size()) {\n           if(mask == target_mask) {\n               if(result.size() == 0 || result.size() >= temp.size()) {\n                   //vector<int> copy = temp;\n                   result = temp;\n               }\n           }\n           return;\n       }\n        \n        if(t[idx][mask] != -1) {\n            if(t[idx][mask] <= temp.size())\n               return ; \n        }\n        \n        if(result.size() != 0 && temp.size() >= result.size()) \n            return; \n        \n        solve(people , idx + 1 , temp , mask ); // no\n\n        if( (mask | people[idx]) != mask) {\n            temp.push_back(idx);\n            solve(people, idx + 1, temp , mask | people[idx]);\n\n            temp.pop_back();\n            t[idx][mask] = (temp.size() != 0 ) ? temp.size() : -1;\n        }\n\n    }\n    \n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        n = req_skills.size();                                                                                          \n        m = people.size();\n        \n        unordered_map<string, int> skills; //skill -> unique number\n        for (int i = 0; i < n; ++i)\n            skills[req_skills[i]] = i;\n        \n        // represent each person by a single bitmasked number (k\'th bit represents if a person has the k\'th skill or not)\n        vector<int> people_skill;\n        for (auto &v: people) {\n            int skill_bit = 0;\n            for (string &skill: v)\n                skill_bit |= 1 << skills[skill];\n            \n            people_skill.push_back(skill_bit);\n        }\n        \n        // required set of skills mask (All set to 1s)\n        target_mask = pow(2, n) - 1;\n\n        t.resize(62, vector<int>(target_mask+1, -1));\n        vector<int> temp;\n        solve(people_skill, 0, temp, 0);\n        return result;\n    }\n};\n\n```
[]