[LeetCode The Hard Way]  DP +  Bit Masking
Please check out LeetCode The Hard Way for more solution explanations and tutorials. If you like it, please give a star and watch my Github Repository.\n\n---\n
Please check out [LeetCode The Hard Way](https://wingkwong.github.io/leetcode-the-hard-way/) for more solution explanations and tutorials. If you like it, please give a star and watch my [Github Repository](https://github.com/wingkwong/leetcode-the-hard-way).\n\n---\n\nSince the skills are strings, we need to digitise them first. For example, given req_skills = ["java","nodejs","reactjs"], we can turn it to [0, 1, 2] where each number map the corresponding skill. Let `dp[i]` be the number of people for the mask `i` and `ans[j]` be the list of people chosen for mask `j`. We iterate each people to calculate its skills and iterate each mask to see if adding this person to the team from the old mask could have a smaller team size for the new mask. If so, update `dp` and add this person to ans.\n\n```cpp\nclass Solution {\npublic:\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        int n = req_skills.size(), m = people.size();\n        // digitize skills\n        unordered_map<string, int> skills;\n        for (int i = 0; i < n; i++) skills[req_skills[i]] = i;\n        // dp[mask] : number of people for mask\n        vector<int> dp(1 << n, 1e9);\n        // ans[mask] : the list of people for mask\n        vector<vector<int>> ans(1 << n);\n        dp[0] = 0;\n        // iterate people\n        for (int i = 0; i < m; i++) {\n            // skills for the i-th person\n            int p_skill = 0;\n            for (auto s : people[i]) p_skill |= (1 << skills[s]);\n            // compute with previous masks\n            for (int mask = 0; mask < (1 << n); mask++) {\n                // create a new mask\n                int new_mask = mask | p_skill;\n                // check if there is a smaller team for the new_mask\n                if (dp[mask] + 1 < dp[new_mask]) {\n                    dp[new_mask] = dp[mask] + 1;\n                    // take the people from mask\n                    ans[new_mask] = ans[mask];    \n                    // and add the i-th person\n                    ans[new_mask].push_back(i);\n                }\n            }\n        } \n        return ans[(1 << n) - 1];\n    }\n};\n```\n
['Dynamic Programming', 'Bitmask', 'C++']