[Java/C++/Python] DP Solution
Intuition\nThe goal is to find the smallest team of people that can cover all of the required skills.\nWe can apply dp solution, where\ndp[skills] is a sufficie
# **Intuition**\nThe goal is to find the smallest team of people that can cover all of the required skills.\nWe can apply dp solution, where\n`dp[skills]` is a sufficient team to satisfy a required `skills` set.\n<br>\n\n# **Explanation**\n\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.\n`req_skills[0]` is `1 << 0`\n`req_skills[i]` is `1 << 1`\n`req_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`.\n`dp[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<br>\n\n# **Complexity**\nTime `O(people * 2^skill)`\nSpace `O(2^skill)`\n<br>\n\n\n**Java:**\n```java\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        int n = req_skills.length, m = people.size();\n        HashMap<String, Integer> skill_index = new HashMap<>();\n        for (int i = 0; i < n; ++i)\n            skill_index.put(req_skills[i], i);\n        List<Integer>[] dp = new List[1 << n];\n        dp[0] = new ArrayList<>();\n        for (int i = 0; i < m; ++i) {\n            int cur_skill = 0;\n            for (String s : people.get(i))\n                cur_skill |= 1 << skill_index.get(s);\n            for (int prev = 0; prev < dp.length; ++prev) {\n                if (dp[prev] == null) continue;\n                int comb = prev | cur_skill;\n                if (dp[comb] == null || dp[prev].size() + 1 < dp[comb].size()) {\n                    dp[comb] = new ArrayList<>(dp[prev]);\n                    dp[comb].add(i);\n                }\n            }\n        }\n        return dp[(1 << n) - 1].stream().mapToInt(i -> i).toArray();\n    }\n```\n\n**C++:**\n```cpp\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```\n\n**Python:**\n```python\n    def smallestSufficientTeam(self, req_skills, people):\n        n, m = len(req_skills), len(people)\n        skill_index = {v: i for i, v in enumerate(req_skills)}\n        dp = {0: []}\n        for i, p in enumerate(people):\n            cur_skill = 0\n            for skill in p:\n                if skill in skill_index:\n                    cur_skill |= 1 << skill_index[skill]\n            for prev, need in dict(dp).items():\n                comb = prev | cur_skill\n                if comb == prev: continue\n                if comb not in dp or len(dp[comb]) > len(need) + 1:\n                    dp[comb] = need + [i]\n        return dp[(1 << n) - 1]\n```\n
['C', 'Python', 'Java']