BFS / 91% beats / optimal /explained code
\n\n# Approach\n\n# BFS + Bitmasking\n\n# Complexity\n- Time complexity:\nO(2^n)\n- Space complexity:\nO(m.2^n)\n# Code\n\nclass Solution {\npublic:\n    vector
\n\n# Approach\n\n# BFS + Bitmasking\n\n# Complexity\n- Time complexity:\nO(2^n)\n- Space complexity:\nO(m.2^n)\n# Code\n```\nclass Solution {\npublic:\n    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n        const int n = (int)req_skills.size();\n        \n        // Map skills to their corresponding bitmask values\n        map<string, int> skill_to_bitmask;\n        for (int i = 0; i < n; i++) {\n            skill_to_bitmask[req_skills[i]] = (1 << i);\n        }\n        \n        vector<int> people_bitmasks;\n        \n        // Convert each person\'s skills to a bitmask\n        for (auto& person_skills : people) {\n            int bitmask = 0;\n            for (auto& skill : person_skills) {\n                if (skill_to_bitmask.find(skill) != skill_to_bitmask.end()) {\n                    bitmask |= skill_to_bitmask[skill];\n                }\n            }\n            people_bitmasks.push_back(bitmask);\n        }\n        \n        vector<int> distance(1 << n, -1);  // Store the shortest distance for each bitmask\n        vector<pair<int, int>> parent(1 << n, {-1, -1});  // Store the parent information for backtracking\n        queue<int> q;\n        \n        // Perform BFS to find the shortest path\n        q.emplace(0);\n        distance[0] = 0;\n        while (!q.empty()) {\n            int u = q.front();\n            q.pop();\n            for (int i = 0; i < (int)people_bitmasks.size(); i++) {\n                int v = u | people_bitmasks[i];\n                if (distance[v] == -1) {\n                    parent[v] = {u, i};\n                    distance[v] = distance[u] + 1;\n                    q.emplace(v);\n                } \n            }\n        }\n        \n        // Backtracking to retrieve the team members\n        vector<int> team;\n        int x = (1 << n) - 1;\n        while (parent[x].first != -1) {\n            team.push_back(parent[x].second);\n            x = parent[x].first;\n        }\n\n        assert(distance[(1 << n) - 1] == (int)team.size());  // Sanity check\n        return team;\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']