Using Bit Manipulation | C++ | DP
Approach\n Describe your approach to solving the problem. \n- A list of people is needed. As the maximum number of people is 60 , instead of storing the indices
# Approach\n<!-- Describe your approach to solving the problem. -->\n- A list of people is needed. As the maximum number of people is 60 , instead of storing the indices of people in the team we can use bitmasking of 64 bit integer to keep track of the people in the team.\n- For ex: if 1,3,6 indices people are in a team , then 000001001010.\n- Number of set bits gives the number of the people in a team.\n- For each person, the set of skills he/she possesses can be stored as bitmasking of a 32 bit integer since maximum number of skills is 16.\n- Total combined skills of all the people in a team can be known by taking bitwise or of the bitmasking representation of skills of each individual in a team.\n\n\n# Complexity\n- Time complexity: $$O(n*(1<<16))$$\n n --> number of people\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(n*(1<<16))$$\n n --> number of people\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n \n# Code\n```\nclass Solution {\npublic:\n\n    int countBits(long long x){\n     // counts the number of set bits in a long long int\n        int count=0;\n        for(int i=0;i<64;i++){\n            if(x&(1LL<<i)) count++;\n        }\n        return count;\n    }\n    long long findMin(int i,int skills,int allSkills,vector<int>&peo,vector<vector<long long>>&dp){\n      if(i==peo.size()){\n             if(skills!=allSkills) {\n                return (1LL<<i)-1LL;\n             }\n             return 0LL;\n         }\n         if(dp[i][skills]!=-1) return dp[i][skills];\n         int temp=skills;\n         long long notPick=findMin(i+1,skills,allSkills,peo,dp);\n         temp|=peo[i];\n         if(temp==skills) return notPick;\n         long long pick=findMin(i+1,temp,allSkills,peo,dp);\n        \n         pick|=(1LL<<i);\n        int x=countBits(pick);\n        int y=countBits(notPick);\n        if(x<y) return dp[i][skills]=pick;\n        return dp[i][skills]=notPick;\n         \n         \n    }\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        map<string,int>m;\n        int n=req_skills.size();\n        for(int i=0;i<n;i++){\n            m[req_skills[i]]=i;\n        }\n        vector<int>peo(people.size(),0);\n        for(int i=0;i<peo.size();i++){\n            for(auto str:people[i]){\n                peo[i]|=(1<<m[str]);\n            }\n        }\n        \n        int allSkills=(1<<n)-1;\n        \n             vector<vector<long long>>dp(peo.size(),vector<long long>(allSkills+1,-1));\n        long long ans= findMin(0,0,allSkills,peo,dp);\n        vector<int>res;\n        for(int i=0;i<64;i++){\n            if(ans&(1LL<<i)) res.push_back(i);\n        }\n   \n        return res;\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']