🚀 [VIDEO] Faster than 90%🔥| ❗Long Explanation❗ | 2-D DP + BITMASK | Clean Code
\uD83C\uDF1F Intuition\n Describe your first thoughts on how to solve this problem. \n\nMy initial intuition for solving this problem is to use a dynamic progra
# \uD83C\uDF1F Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nMy initial intuition for solving this problem is to use a dynamic programming approach. Since we need to find the smallest sufficient team, it seems logical to consider all possible combinations of people and skills. By using a dynamic programming table to keep track of the skills covered by each team, we can gradually build up the solution.\n\nhttps://youtu.be/RJnReFN_nJE\n\n# \uD83D\uDCA1 Approach\n<!-- Describe your approach to solving the problem. -->\n\nHere is the approach I would take to solve the "Smallest Sufficient Team" problem:\n\n1. First, I would create a skill mapping that maps each skill to its corresponding index. This mapping will help us represent skills using bitmasks later on.\n\n2. Next, I would initialize a dynamic programming table called `dp` with one entry: 0, representing no skills covered and no team members selected.\n\n3. Then, I would iterate over each person in the `people` list. For each person, I would create a bitmask to represent their skills. This bitmask will have a 1 in the positions corresponding to the skills they possess.\n\n4. Within the person iteration, I would iterate over the existing teams in the `dp` table. For each team, I would combine the skills of the current person with the team\'s skills using the bitwise OR operator. If the new combined skills cover more skills or have a smaller size than the existing team, I would update the team in the `dp` table.\n\n5. Finally, I would return the team from the `dp` table that covers all the required skills. The required skills are represented by a bitmask where all the skill positions have a 1.\n\n# \u23F0 Complexity\n- Time complexity: \nThe time complexity of this approach is O(N * (2^M)), where N is the number of people and M is the number of required skills. This is because we iterate over each person (N) and for each person, we iterate over the existing teams (2^M) in the `dp` table.\n\n- Space complexity: \nThe space complexity is O(2^M) as we need to store the dynamic programming table `dp` that can have up to 2^M entries, where M is the number of required skills.\n\n# \uD83D\uDCDD Code\n```Python []\nclass Solution:\n    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n        # Map skills to their indices\n        skill_map = {skill: i for i, skill in enumerate(req_skills)}\n        n = len(req_skills)\n        # dp bitmask representing the skills covered by each team\n        dp = {0: []}\n        for i, person in enumerate(people):\n            # Bitmask representing the skills of the current person\n            person_skill_mask = 0\n            for skill in person:\n                # Set the corresponding bit for each skill\n                person_skill_mask |= (1 << skill_map[skill])\n            # Iterate over existing teams\n            for skill_mask, team in list(dp.items()):\n                # Combine the skills of the current person with the existing team\n                new_mask = skill_mask | person_skill_mask\n                if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:\n                    # Update the team if it covers more skills or has a smaller size\n                    dp[new_mask] = team + [i]\n        # Return the team that covers all the required skills\n        return dp[(1 << n) - 1]\n```\n``` JavaScript []\nvar smallestSufficientTeam = function(req_skills, people) {\n    let skill_map = {};\n    let n = req_skills.length;\n    for (let i = 0; i < n; ++i) {\n        skill_map[req_skills[i]] = i;\n    }\n\n    let dp = [];\n    dp[0] = [];\n\n    for (let i = 0; i < people.length; ++i) {\n        let person_skill_mask = 0;\n        for (let skill of people[i]) {\n            person_skill_mask |= (1 << skill_map[skill]);\n        }\n\n        for (let skill_mask = 0; skill_mask < (1 << n); ++skill_mask) {\n            if ((dp[skill_mask] === undefined || dp[skill_mask].length == 0) && skill_mask != 0) continue;\n            let new_mask = skill_mask | person_skill_mask;\n            if (dp[new_mask] === undefined || dp[new_mask].length > dp[skill_mask].length + 1) {\n                dp[new_mask] = [...dp[skill_mask], i];\n            }\n        }\n    }\n\n    return dp[(1 << n) - 1];    \n};\n```\n``` Java []\nclass Solution {\n    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {\n        Map<String, Integer> skill_map = new HashMap<>();\n        int n = req_skills.length;\n        for (int i = 0; i < n; ++i) {\n            skill_map.put(req_skills[i], i);\n        }\n        \n        List<Integer>[] dp = new ArrayList[1 << n];\n        dp[0] = new ArrayList<>();\n\n        for (int i = 0; i < people.size(); ++i) {\n            int person_skill_mask = 0;\n            for (String skill : people.get(i)) {\n                person_skill_mask |= (1 << skill_map.get(skill));\n            }\n\n            for (int skill_mask = 0; skill_mask < (1 << n); ++skill_mask) {\n                if (dp[skill_mask] == null && skill_mask != 0) continue;\n                int new_mask = skill_mask | person_skill_mask;\n                if (dp[new_mask] == null || dp[new_mask].size() > dp[skill_mask].size() + 1) {\n                    dp[new_mask] = new ArrayList<>(dp[skill_mask]);\n                    dp[new_mask].add(i);\n                }\n            }\n        }\n\n        int[] res = new int[dp[(1 << n) - 1].size()];\n        for (int i = 0; i < res.length; i++) {\n            res[i] = dp[(1 << n) - 1].get(i);\n        }\n        return res;\n    }\n}\n```\n``` C# []\npublic class Solution {\n    public int[] SmallestSufficientTeam(string[] req_skills, IList<IList<string>> people) {\n        Dictionary<string, int> skill_map = new Dictionary<string, int>();\n        int n = req_skills.Length;\n        for (int i = 0; i < n; ++i) {\n            skill_map[req_skills[i]] = i;\n        }\n\n        List<int>[] dp = new List<int>[1 << n];\n        dp[0] = new List<int>();\n\n        for (int i = 0; i < people.Count; ++i) {\n            int person_skill_mask = 0;\n            foreach (string skill in people[i]) {\n                person_skill_mask |= (1 << skill_map[skill]);\n            }\n\n            for (int skill_mask = 0; skill_mask < (1 << n); ++skill_mask) {\n                if (dp[skill_mask] == null && skill_mask != 0) continue;\n                int new_mask = skill_mask | person_skill_mask;\n                if (dp[new_mask] == null || dp[new_mask].Count > dp[skill_mask].Count + 1) {\n                    dp[new_mask] = new List<int>(dp[skill_mask]);\n                    dp[new_mask].Add(i);\n                }\n            }\n        }\n\n        return dp[(1 << n) - 1].ToArray();\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    std::vector<int> smallestSufficientTeam(std::vector<std::string>& req_skills, std::vector<std::vector<std::string>>& people) {\n        std::unordered_map<std::string, int> skill_map;\n        int n = req_skills.size();\n        for (int i = 0; i < n; ++i) {\n            skill_map[req_skills[i]] = i;\n        }\n\n        std::vector<std::vector<int>> dp(1 << n);\n        dp[0] = std::vector<int>();\n\n        for (int i = 0; i < people.size(); ++i) {\n            if (people[i].empty()) continue; // Skip people with no skills\n\n            int person_skill_mask = 0;\n            for (const std::string& skill : people[i]) {\n                person_skill_mask |= (1 << skill_map[skill]);\n            }\n\n            for (int skill_mask = 0; skill_mask < (1 << n); ++skill_mask) {\n                if (dp[skill_mask].empty() && skill_mask != 0) continue;\n                int new_mask = skill_mask | person_skill_mask;\n                if (dp[new_mask].empty() || dp[new_mask].size() > dp[skill_mask].size() + 1) {\n                    dp[new_mask] = dp[skill_mask];\n                    dp[new_mask].push_back(i);\n                }\n            }\n        }\n\n        return dp[(1 << n) - 1];\n    }\n};\n```
['C++', 'Java', 'Python3', 'JavaScript', 'C#']