C++ | DP | Bitmask | Easy to Understand | Optimal | Hard Problem | 1125. Smallest Sufficient Team
C++ | DP | Bitmask | Easy to Understand | Optimal | Hard Problem | 1125. Smallest Sufficient Team\n\nclass Solution {\npublic:\n    vector<int> smallestSufficie
# C++ | DP | Bitmask | Easy to Understand | Optimal | Hard Problem | 1125. Smallest Sufficient Team\n```\nclass Solution {\npublic:\n    vector<int> smallestSufficientTeam(vector<string>& req, vector<vector<string>>& a)\n    {\n        int n = req.size();\n        \n        map<string,int>m;\n        \n        for(int i=0;i<req.size();i++)\n        {\n            m[req[i]] = i;\n        }\n        \n        vector<vector<int>>v;\n        \n        for(int i=0;i<a.size();i++)\n        {\n            vector<int>t;\n            for(int j=0;j<a[i].size();j++)\n            {\n                t.push_back(m[a[i][j]]);\n            }\n            v.push_back(t);\n        }\n        \n        unordered_map<int,vector<int>>dp;\n         \n        dp.reserve(1<<n);\n        dp[0] = {};\n        \n        for(int i=0;i<v.size();i++)\n        {\n            int cur_skill = 0;\n            for(int j=0;j<v[i].size();j++)\n            {\n                  cur_skill = (cur_skill)|(1<<v[i][j]);\n            } \n            \n            for(auto it = dp.begin(); it!= dp.end() ;it++)\n            {\n                int comb = (cur_skill)|(it->first);\n                if(dp.find(comb)==dp.end() or dp[comb].size()>1+dp[it->first].size())\n                {\n                    dp[comb] = it->second;\n                    dp[comb].push_back(i);\n                }\n            }\n        } \n        \n        return dp[(1<<n)-1];\n    }\n};\n```
['Dynamic Programming', 'C', 'Bitmask', 'C++']