1
class Solution {
2
 public:
3
  std::vector<int> smallestSufficientTeam(std::vector<std::string> &req_skills,
4
                                          std::vector<std::vector<std::string>> &people) {
5
    int n = req_skills.size();
6
    int m = people.size();
7

8
    std::unordered_map<std::string, int> skillToIndex;
9
    for (int i = 0; i < n; i++) {
10
      skillToIndex[req_skills[i]] = i;
11
    }
12

13
    std::vector<int> arr(m, 0);
14
    for (int i = 0; i < m; i++) {
15
      std::vector<std::string> &personSkills = people[i];
16
      int val = 0;
17
      for (const std::string &skill : personSkills) {
18
        val |= 1 << skillToIndex[skill];
19
      }
20
      arr[i] = val;
21
    }
22

23
    std::vector<bool> banned(m, false);
24
    for (int i = 0; i < m; i++) {
25
      for (int j = i + 1; j < m; j++) {
26
        int val = arr[i] | arr[j];
27
        if (val == arr[i]) {
28
          banned[j] = true;
29
        } else if (val == arr[j]) {
30
          banned[i] = true;
31
        }
32
      }
33
    }
34

35
    std::vector<int> ans;
36
    helper(0, n, arr, std::vector<int>(), banned, ans);
37

38
    return ans;
39
  }
40

41
 private:
42
  void helper(int cur, int n, const std::vector<int> &arr, std::vector<int> team,
43
              const std::vector<bool> &banned, std::vector<int> &ans) {
44
    if (cur == (1 << n) - 1) {
45
      if (ans.empty() || team.size() < ans.size()) {
46
        ans = team;
47
      }
48
      return;
49
    }
50

51
    if (!ans.empty() && team.size() >= ans.size()) {
52
      return;
53
    }
54

55
    int zero = 0;
56
    while (((cur >> zero) & 1) == 1) {
57
      zero++;
58
    }
59

60
    for (int i = 0; i < arr.size(); i++) {
61
      if (banned[i]) {
62
        continue;
63
      }
64

65
      if (((arr[i] >> zero) & 1) == 1) {
66
        team.push_back(i);
67
        helper(cur | arr[i], n, arr, team, banned, ans);
68
        team.pop_back();
69
      }
70
    }
71
  }
72
};