C++ || BFS with BitMask 👌👍
\n# Complexity\n- Time complexity: O(people * 2^skill)\n\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(2^skill)\n Add your space complexi
\n# Complexity\n- Time complexity: O(people * 2^skill)\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(2^skill)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n     unordered_map<string, int> skill2idx;\n\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        int target = std::pow(2, (int)req_skills.size())-1;\n        for (int i=0; i<req_skills.size(); i++){\n            skill2idx[req_skills[i]] = i;\n        }\n        return bfs(target, people);\n    }\n    int computeMask(vector<string>& skills){\n        int mask = 0;\n        for (string skill : skills){\n            mask |= (1<<skill2idx[skill]);\n        }\n        return mask;\n    }\n    vector<int> bfs(int target, vector<vector<string>>& people){\n        deque<pair<int, vector<int>>> q;\n        vector<int> start;\n        q.push_back(std::make_pair(0, start));\n        std::unordered_set<int> seen;\n        seen.insert(0);\n        while (!q.empty()){\n            auto curPair = q.front(); q.pop_front();\n            int curMask = curPair.first;\n            vector<int> curTeam = curPair.second;\n            if (curMask==target){return curTeam;}\n            for (int i=0; i<people.size(); i++){\n                vector<int> nxtTeam = vector<int>(curTeam.begin(), curTeam.end());\n                nxtTeam.push_back(i);\n                int nxtMask = curMask | computeMask(people[i]);\n                if (seen.count(nxtMask)==0){\n                    seen.insert(nxtMask);\n                    q.push_back(std::make_pair(nxtMask, nxtTeam));\n                }\n            }\n        }\n        return {};\n    }\n};\n```
['C++']