1
class Solution {
2
  public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
3
    int N = 1 << req_skills.length, INF = (int) 1e9;
4
    int[] parent = new int[N];
5
    int[] who = new int[N];
6
    int[] dp = new int[N];
7
    Arrays.fill(dp, INF);
8
    dp[0] = 0;
9
    for (int i = 0; i < N; i++) {
10
      if (dp[i] != INF) { // valid state
11
        for (int k = 0; k < people.size(); k++) {
12
          int cur = i;
13
          for (int j = 0; j < req_skills.length; j++) {
14
            for (String skill : people.get(k)) {
15
              if (req_skills[j].equals(skill)) {
16
                cur |= 1 << j; // set the mask
17
                break;
18
              }
19
            }
20
          }
21
          if (dp[cur] > dp[i] + 1) { // replace if better
22
            dp[cur] = dp[i] + 1;
23
            parent[cur] = i;
24
            who[cur] = k;
25
          }
26
        }
27
      }
28
    }
29
    int[] ans = new int[dp[N - 1]];
30
    for (int i = 0, cur = N - 1; i < ans.length; i++) {
31
      ans[i] = who[cur];
32
      cur = parent[cur];
33
    }
34
    return ans;
35
  }
36
}