1125. Smallest Sufficient Team
Intuition\nThe goal is to find the smallest team of people that can cover all of the required skills. We can apply dp solution, where\ndp[skills] is a sufficien
# Intuition\nThe goal is to find the smallest team of people that can cover all of the required skills. We can apply dp solution, where\ndp[skills] is a sufficient team to satisfy a required skills set.\n\n# Approach\nFirst creates a map of skills to skill index,\nso that it can quickly look up which skill corresponds to which index.\n\nWe use the bit mask to represent a skills set.\nreq_skills[0] is 1 << 0\nreq_skills[i] is 1 << 1\nreq_skills[n - 1] is 1 << (n - 1)\nThen a skills set can be expressed as an integer bit mask.\n\nThen creates a hashmap dp for size 1 << n.\ndp[skills] will contain the indices of the people required to satisfy the skills.\n\nWe loops through the people,\nand for each person, find his cur_skill bit mask.\nThen we check all dp[prev] in the existing dp.\nwe combine the new skills comb = prev | cur_skill\nand then check if dp[comb] not found or dp[comb].size() > 1 + dp[prev].size(),\nthen we can update dp[comb] by dp[prev] + [this person]\n\nWe continuly do this and finally,\nreturns the indices of the people dp[(1 << n) - 1] with all skills covered.\n\n# Complexity\n- Time complexity:\nO(people * 2^skill)\n\n- Space complexity:\nO(2^skill)\n# Code\n```\nclass Solution {\npublic:\n       vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        int n = req_skills.size();\n        unordered_map<int, vector<int>> dp;\n        dp.reserve(1 << n); // reserve space and avoid hash collisions\n        dp[0] = {};\n        unordered_map<string, int> skill_index;\n        for (int i = 0; i < req_skills.size(); ++i)\n            skill_index[req_skills[i]] = i;\n        for (int i = 0; i < people.size(); ++i) {\n            int cur_skill = 0;\n            for (auto& skill: people[i])\n                cur_skill |= 1 << skill_index[skill];\n            for (auto it = dp.begin(); it != dp.end(); ++it) {\n                int comb = it->first | cur_skill;\n                if (dp.find(comb) == dp.end() || dp[comb].size() > 1 + dp[it->first].size()) {\n                    dp[comb] = it->second;\n                    dp[comb].push_back(i);\n                }\n            }\n        }\n        return dp[(1 << n) - 1];\n    }\n};\nplease upvote if you like the solution\n```
['Bitmask', 'C++']