C++✅✅ | Beginner Friendly 🎗️| DP+BITMASKING 🔥| Faster than 90% of Sol^n 🚀| Clean and Concise🙌
CONNECT WITH ME ON LINKEDIN : https://www.linkedin.com/in/kunal-shaw-/\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approac
**CONNECT WITH ME ON LINKEDIN : https://www.linkedin.com/in/kunal-shaw-/**\n\n# 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:O(2^m)->m is size of people vector\n\n- Space complexity:O(2^m)->m is size of people vector\n\n# Code\n```\n#define ll long long int\nclass Solution {\npublic:\n    unordered_map<string, ll> dp;\n    ll f(ll i,vector<ll> &hash,ll mask,ll n){\n        if(mask==(1<<n)-1) return 0;\n        if(i>=hash.size()){\n            return INT_MAX;\n        }\n        string key=to_string(i)+" "+to_string(mask);\n        if(dp.count(key)) return dp[key];\n        ll ans=INT_MAX;\n        ll pick=f(i+1,hash,mask|hash[i],n);\n        ll nonpick=f(i+1,hash,mask,n);\n        if (__builtin_popcountll(pick)<__builtin_popcountll(nonpick)) ans=pick|(1LL<<i);\n        else ans=nonpick;\n        return dp[key]=ans;\n    }\n    vector<int> smallestSufficientTeam(vector<string>& req, vector<vector<string>>& peo) {\n        ll n=req.size();\n        ll m=peo.size();\n        map<string,ll> mp;\n        for(int i=0;i<n;i++){\n            mp[req[i]]=(1<<i);\n        }\n        vector<ll> hash;\n        for(int i=0;i<m;i++){\n            int mask=0;\n            for(auto x:peo[i]){\n                mask=mask|mp[x];\n            }\n            hash.push_back(mask);\n        }\n        ll cnt=f(0,hash,0,n);\n        vector<int> ans;\n        int idx=0;\n        while(cnt>0) {\n            ll pick=cnt&1;\n            if (pick==1) {\n                ans.push_back(idx);\n            }\n            idx++;\n            cnt=cnt/2;\n        }\n        return ans;\n    }\n};\n```\n![memer-cat.jpg](https://assets.leetcode.com/users/images/dfc2018d-01d8-43da-9889-af2896179f15_1675779280.3429081.jpeg)\n\n
['Hash Table', 'String', 'Dynamic Programming', 'Bit Manipulation', 'C++']