C++ recursive DP+ bitMask
Intuition\n Describe your first thoughts on how to solve this problem. \nThis code uses dynamic programming to find the smallest sufficient team of people who p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis code uses dynamic programming to find the smallest sufficient team of people who possess all the required skills. It represents skills using binary masks and iterates through all possible combinations of team members to find the optimal solution. The team function recursively explores all combinations and memoizes the results using the dp vector. The main function transforms the input into bitmasks, initializes the dp vector, and calls the team function to find the smallest sufficient team. The final result is returned as a vector of indices representing the selected team members.\n\nThere is a harder problem using similar method! Only very few people solved it.\n[1994. The Number of Good Subsets\n](https://leetcode.com/problems/the-number-of-good-subsets/solutions/3778433/c-bitmask-dp-with-number-theory/)\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn English subtitles if neccessary]\n[https://youtu.be/WPGsOFaDBqw](https://youtu.be/WPGsOFaDBqw)\nEach skill has a correspondence number. So the unordered_map<string, int> is used for the transformation of strings to ints.\n```\n        // Transform string to numbers\n        unordered_map<string, int> skillnr;\n        for (int i = 0; i < r; i++)\n            skillnr[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 << skillnr[skill]);\n            }\n        //    cout << i << "->" << peoMask[i] << endl;\n        }\n```\nThe crucial part is implemented in the function team. Which persons should be choosen in this team? For implementation the C++ bitset is used. \n```\nint skills = skills_haved & ~peoMask[i];//no skills from person_i\nif (skills != skills_haved) {\n    long long choosen = team(skills) | 1LL << i;//containing person_i\n    bitset<60> bChoosen(choosen);\n    //Check wether fewer people\n    if (bChoosen.count() < bitset<60>(dp[skills_haved]).count())\n        dp[skills_haved] = choosen;\n}\n```\n# How DP\n![how_dp.png](https://assets.leetcode.com/users/images/745896d8-4cbc-4dc6-a901-4ad4d6a74673_1689504188.824045.png)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(2^r * n)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$ O(n + r + 2^r)=O(n+2^r)$\n# Code Runtime 30 ms Beats 95.16%\n```\nclass Solution {\npublic:\n    int r;\n    int n;\n    vector<int> peoMask;\n    vector<long long> dp;\n\n    long long team(int skills_haved) {\n        if (skills_haved == 0) return 0;\n        if (dp[skills_haved] != INT_MAX) return dp[skills_haved];\n        long long ans=INT_MAX;\n        for (int i = 0; i < n; i++) {\n            int skills = skills_haved & ~peoMask[i];//no skills from person_i\n            if (skills != skills_haved) {\n                long long choosen = team(skills) | 1LL << i; //containing person_i\n                bitset<60> bChoosen(choosen);\n                //Check wether fewer people\n                if (bChoosen.count() < bitset<60>(ans).count()){\n                    ans = choosen;\n                }       \n            }\n        }\n        return dp[skills_haved]=ans;\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 string to numbers\n        unordered_map<string, int> skillnr;\n        for (int i = 0; i < r; i++)\n            skillnr[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 << skillnr[skill]);\n            }\n        //    cout << i << "->" << peoMask[i] << endl;\n        }\n\n        // DP\n        dp.assign(1<<r, INT_MAX);\n        long long peoChoosen = team((1<<r)-1);\n        bitset<60> X(peoChoosen);\n        vector<int> ans;\n        for (int i = 0; i < n; i++)\n            if (X[i]) ans.push_back(i);\n\n        return ans;\n    }\n};\n\n\n\n```
['Dynamic Programming', 'Bit Manipulation', 'C++']