C++ | DP |
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int r; // Number of required skills\n    int n; // Number of people\n    vector<int> peoMask; // Bitmasks representing skills of each person\n    vector<long long> dp; // Memoization table\n\n    // Recursive function to find the minimum team\n    long long team(int skills_had) {\n        if (skills_had == 0) return 0; // Base case: no skills required\n        if (dp[skills_had] != INT_MAX) return dp[skills_had]; // Return memoized result if available\n        \n        long long ans = n;\n        for (int i = 0; i < n; i++) {\n            int skills = skills_had & ~peoMask[i]; // Remove skills already covered by person i\n            if (skills != skills_had) {\n                long long chosen = team(skills) | 1LL << i; // Recursively find the minimum team without person i\n                bitset<60> bChosen(chosen);\n\n                // Check if the newly chosen team has fewer people\n                if (bChosen.count() < bitset<60>(dp[skills_had]).count())\n                    dp[skills_had] = chosen; // Update the memoization table with the new minimum team\n            }\n        }\n        return dp[skills_had];\n    }\n\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) \n    {\n        r = req_skills.size();\n        n = people.size();\n\n        // Transform skills from strings to numbers\n        unordered_map<string, int> skill_nr;\n        for (int i = 0; i < r; i++)\n            skill_nr[req_skills[i]] = i;\n\n        peoMask.assign(n, 0);\n        for (int i = 0; i < n; i++) {\n            for (string& skill : people[i]) {\n                peoMask[i] |= (1 << skill_nr[skill]); // Set the corresponding bit for each skill of person i\n            }\n        }\n\n        // DP\n        dp.assign(1<<r, INT_MAX);\n        long long peoChosen = team((1<<r)-1); // Find the minimum team to cover all required skills\n        bitset<60> X(peoChosen);\n        vector<int> ans;\n        for (int i = 0; i < n; i++)\n            if (X[i]) ans.push_back(i); // Add the selected people to the answer\n\n        return ans;\n    }\n};\n\n```
['Array', 'Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']