BitMask DP, fully explained, C++
Intuition\nGiven the small constraints, one thinks immediately of BitMask DP.\nBefore doing anything, we need to numerize the data. This is straightforward usin
# Intuition\nGiven the small constraints, one thinks immediately of BitMask DP.\nBefore doing anything, we need to numerize the data. This is straightforward using a map.\n\n# Approach\nLet $$n = skills.length$$ and $$m = people.length$$\n\nLet \n$$dp[mask][i] = \\text{minimum number of people from } \\lbrack1,i\\rbrack \\text{ to cover the skills represented by on-bits in mask}$$\n\n\n\nNow we can compute \n$$dp[mask][i] = min(dp[newMask][i-1]+1, dp[mask][i-1]) $$\n\nWhere $$newMask = \\text{ mask with all bits covered by person i off}$$\n\n(So for example if $$mask = 1001(2) $$ and person $$i$$ has skills $$0$$ and $$2$$ then $$newMask = 1000(2)$$)\n\nTo recover our answer we can have an array \n$$ans[mask][i] = \\text{ person who we chose to answer the current subproblem}$$\n\nNow\n $ ans[mask][i] = \\begin{cases}\n      i & \\text{if }dp[newMask][i-1]+1 < dp[mask][i-1] \\\\\n      ans[mask][i-1] & \\text{otherwise }\n    \\end{cases}\\, $\n\n\n\n# Complexity\n- Time complexity:\n$$O(2^n\\times m^2)$$\n\n- Space complexity:\n$$O(2^n\\times m^2)$$\n\n# Code\n```\n\n\nclass Solution {\npublic:\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        int n = (req_skills).size();\n        int m = (int)people.size();\n        map<string, int> mapping;\n        for(int i = 0 ; i < n; i++){\n            mapping[req_skills[i]] = i;\n        }\n        vector<vector<int> > v(m);\n        for(int i = 0 ; i < m; i++){\n            for(string s : people[i]){\n                v[i].push_back(mapping[s]);\n            }\n        }\n        vector<vector<int> > dp((1<<n), vector<int> (m, 1e9+7));\n        vector<vector<int> > ans((1<<n), vector<int> (m, -1));\n        //dp[mask][i] = min cost to cover all the tasks marked by mask using first i people\n        //            = min(dp[mask without ones covered by i][i-1], dp[mask][i-1])\n        int first = 0;\n        dp[0][0] = 0;\n        for(int i = 0 ; i < m; i++){\n            dp[0][i] = 0;\n        }\n        for(int mask = 1; mask < (1<<n); mask ++){\n            for(int j = 0 ; j < m; j++){\n                int new_mask = mask;\n                for(int i = 0; i < (int)v[j].size(); i++){\n                    new_mask = new_mask & (~(1 << (v[j][i])));\n                }\n                if(j == 0 && new_mask != 0){\n                    continue;\n                }\n                if(new_mask == 0){\n                    dp[mask][j] = 1;\n                    ans[mask][j] = j;\n                    continue;\n                }\n                if(dp[mask][j-1] <= dp[new_mask][j-1]+1){\n                    dp[mask][j] = dp[mask][j-1];\n                    ans[mask][j] = ans[mask][j-1];\n                }\n                else{\n                    dp[mask][j] = dp[new_mask][j-1]+1;\n                    ans[mask][j] = j;\n                }\n            }\n        }\n        \n        vector<int> answer;\n        int mask = (1<<n)-1;\n        int cur = ans[mask][m-1];\n        int idx = (m-1);\n        cout<<dp[mask][idx]<<endl;\n        while(mask != 0 && idx >= 0){\n            cur = ans[mask][idx];\n            if(cur != -1){\n                answer.push_back(cur);\n                for(int j = 0; j < (int)v[cur].size(); j++){\n                    mask = mask & (~(1<<(v[cur][j])));\n                }\n                \n            }\n            idx--;\n        }\n        return answer;\n        \n        \n\n\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']