[C++] BFS using std::bitset, 44ms (beats 100%)
First, we convert all people-skills to their respective indices. Those will now be indices to a skills-bitset. We also ignore non-required skills.\n\nWe then do
First, we convert all people-skills to their respective indices. Those will now be indices to a skills-bitset. We also ignore non-required skills.\n\nWe then do a basic breadth-first search in the graph with skill-bitsets as nodes and people as edges. The queue keeps track of which people were used to get to each node (also represented as a bitset). We use this both to generate the output once we reach the final state and to restrict the number of people-edges we need to traverse each round. We can assume that all paths in the graph have people in their original index-order, without loss of generality.\n\n```C++\nclass Solution {\nprivate:\n  using Skills = bitset<16>;\n  using People = bitset<60>;\n\n  vector<int> bitsetIndices(People ppl) {\n    vector<int> result;\n    while (ppl.any()) {\n      int i = __builtin_ctzl(ppl.to_ulong()); // count trailing zeros\n      result.push_back(i);\n      ppl.reset(i);\n    }\n    return result;\n  }\n  \npublic:\n  vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {\n    int const RS  = req_skills.size();\n    int const PPL = people.size();\n\n    // Create a skill-bitmask for each person\n    vector<Skills> ppl(PPL, 0);\n    {\n      unordered_map<string, int> reqIndex;\n      for (int i = 0; i < RS; ++i)\n        reqIndex[req_skills[i]] = i;\n      for (int i = 0; i < PPL; ++i)\n        for (auto const& skill : people[i])\n          if (reqIndex.count(skill))\n            ppl[i].set(reqIndex[skill]);\n    }\n\n    Skills const allSkills = pow(2, RS) - 1;\n\n    // Initialize queue and visited hash-set\n    queue<pair<Skills, People>> q;\n    unordered_set<Skills> visited;\n    q.push({ 0, 0 });\n    visited.insert(0);\n\n    // Breadth First Search\n    for (int count = 0; !q.empty(); ++count) {\n      int q_size = q.size();\n      for (int i = 0; i < q_size; ++i) {\n        Skills skills = q.front().first;\n        People people = q.front().second;\n        q.pop();\n        int lastPerson = people.any() ? log2(people.to_ullong()) : -1;\n        for (int p = lastPerson + 1; p < PPL; ++p) {\n          auto newSkills = skills | ppl[p];\n          auto newPeople = people | People(1ull << p);\n          if (visited.count(newSkills)) continue;\n          if (newSkills == allSkills) return bitsetIndices(newPeople);\n          visited.insert(newSkills);\n          q.push({ newSkills, newPeople });\n        }\n      }\n    }\n\n    // An existing answer was guaranteed in the problem statement\n    assert(false);\n  }\n};\n```
['Breadth-First Search', 'C']