Formatted question description: https://leetcode.ca/all/1125.html

# 1125. Smallest Sufficient Team (Hard)

In a project, you have a list of required skills `req_skills`

, and a list of `people`

. The i-th person `people[i]`

contains a list of skills that person has.

Consider a *sufficient team*: a set of people such that for every required skill in `req_skills`

, there is at least one person in the team who has that skill. We can represent these teams by the index of each person: for example, `team = [0, 1, 3]`

represents the people with skills `people[0]`

, `people[1]`

, and `people[3]`

.

Return **any** sufficient team of the smallest possible size, represented by the index of each person.

You may return the answer in any order. It is guaranteed an answer exists.

**Example 1:**

Input:req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]Output:[0,2]

**Example 2:**

Input:req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]Output:[1,2]

**Constraints:**

`1 <= req_skills.length <= 16`

`1 <= people.length <= 60`

`1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16`

- Elements of
`req_skills`

and`people[i]`

are (respectively) distinct. `req_skills[i][j], people[i][j][k]`

are lowercase English letters.- Every skill in
`people[i]`

is a skill in`req_skills`

. - It is guaranteed a sufficient team exists.

**Related Topics**:

Dynamic Programming, Bit Manipulation

## Solution 1. DP

This looks like a knapsack problem. Let’s try to use DP.

To represent which skills each people have, we can use bitmask. For example, `0110`

means that this people have 1 and 2 skills but doesn’t have 0 and 4 skills.

Let’s first turn the skills from strings to number IDs using `unordered_map<string, int> m`

.

Then `vector<int> p`

stores the bitmasks of the skills of each people.

Let `dp[state][j + 1]`

be the min number of people required for skills represented by `state`

if we only use people `0`

to `j`

.

For `dp[state][j + 1]`

, we have two choices:

- Skip people
`j`

, then`dp[state][j + 1] = dp[state][j]`

- Pick people
`j`

, then`dp[state][j + 1] = dp[prevState][j] + 1`

, where`prevState`

is`state`

subtracting all the skills people`j`

has.

```
dp[state][j] = min(
dp[state][j], // If we skip people `j`
dp[prevState][j] + 1 // If we pick people `j`
)
dp[0][j] = 0
```

`dp[(1 << M) - 1][N]`

is the size of the answer.

To reconstruct the answer, we can start from `state = (1 << M) - 1, j = N - 1`

.

- If
`dp[state][j + 1] == dp[state][j]`

, it means that we should skip people`j`

. - Otherwise, we should pick people
`j`

. So we push`j`

into the answer, and subtract the skills people`j`

has from the`state`

.

We loop until `state == 0`

.

```
// OJ: https://leetcode.com/problems/smallest-sufficient-team/
// Time: O(2^M * N) where M is the size of `req_skills`, N is the number of people
// Space: O(2^M * N)
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> m;
int M = 0, N = people.size();
for (auto &s : req_skills) m[s] = M++;
vector<int> p(N);
for (int i = 0; i < N; ++i) {
for (auto &s : people[i]) {
p[i] |= 1 << m[s];
}
}
vector<vector<int>> dp(1 << M, vector<int>(N + 1, N));
for (int i = 0; i <= N; ++i) dp[0][i] = 0;
for (int state = 0; state < 1 << M; ++state) {
for (int j = 0; j < N; ++j) {
int prev = state & ~p[j];
dp[state][j + 1] = min(dp[state][j], dp[prev][j] + 1);
}
}
vector<int> ans;
int state = (1 << M) - 1, j = N - 1;
for (; state; --j) {
if (dp[state][j + 1] == dp[state][j]) continue;
ans.push_back(j);
state &= ~p[j];
}
return ans;
}
};
```

## Solution 2. DP

Let `dp[state]`

be the min number of people we required for skills represented by `state`

.

To get the optimal value of `dp[state]`

, we try each people `j`

.

```
dp[state] = min( dp[prevState(j)] + 1 | prevState(j) = state & ~p[j] && 0<= j < N )
dp[0] = 0
```

`dp[(1 << M) - 1]`

is the size of the answer.

To reconstruct the answer, we use `pick[state]`

to store the people we should pick given `state`

, and `prevState[state]`

to store the state before we pick people `pick[state]`

.

```
// OJ: https://leetcode.com/problems/smallest-sufficient-team/
// Time: O(2^M * N) where M is the size of `req_skills`, N is the number of people
// Space: O(2^M + N)
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> m;
int M = 0, N = people.size();
for (auto &s : req_skills) m[s] = M++;
vector<int> p(N);
for (int i = 0; i < N; ++i) {
for (auto &s : people[i]) {
p[i] |= 1 << m[s];
}
}
vector<int> dp(1 << M, N), pick(1 << M, -1), prevState(1 << M);
dp[0] = 0;
for (int state = 0; state < 1 << M; ++state) {
for (int j = 0; j < N; ++j) {
int prev = state & ~p[j];
if (dp[prev] + 1 < dp[state]) {
dp[state] = dp[prev] + 1;
pick[state] = j;
prevState[state] = prev;
}
}
}
vector<int> ans;
int state = (1 << M) - 1;
while (pick[state] != -1) {
ans.push_back(pick[state]);
state = prevState[state];
}
return ans;
}
};
```

```
// OJ: https://leetcode.com/problems/smallest-sufficient-team/
// Time: O(2^M * N) where M is the size of `req_skills`, N is the number of people
// Space: O(2^M + N)
// Ref: https://leetcode.com/problems/smallest-sufficient-team/discuss/342120/C%2B%2B-DP-32ms-DP-solution.-Easy-to-implement
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> m;
int M = req_skills.size(), N = people.size();
for (int i = 0; i < M; ++i) m[req_skills[i]] = i;
vector<int> p(N), dp(1 << M, INT_MAX), pick(1 << M, -1), prevState(1 << M);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
for (auto &s : people[i]) {
p[i] |= (1 << m[s]);
}
}
for (int state = 0; state < 1 << M; ++state) {
for (int j = 0; j < N; ++j) {
if (dp[state] == INT_MAX) continue;
int next = state | p[j];
if (dp[next] > dp[state] + 1) {
pick[next] = j;
prevState[next] = state;
dp[next] = dp[state] + 1;
}
}
}
int state = (1 << M) - 1;
vector<int> ans;
while (pick[state] != -1) {
ans.push_back(pick[state]);
state = prevState[state];
}
return ans;
}
};
```

Java

```
class Solution {
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
int skills = req_skills.length, peopleCount = people.size();
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < skills; i++)
map.put(req_skills[i], i);
int[] masks = new int[peopleCount];
for (int i = 0; i < peopleCount; i++)
masks[i] = getMask(people.get(i), map);
int[] dp = new int[1 << skills];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
int[] prevState = new int[1 << skills];
int[] prevPerson = new int[1 << skills];
for (int i = 0; i < peopleCount; i++) {
int mask = masks[i];
for (int j = (1 << skills) - 1; j >= 0; j--) {
if (dp[j] != Integer.MAX_VALUE) {
int newState = j | mask;
if (dp[newState] > dp[j] + 1) {
dp[newState] = dp[j] + 1;
prevState[newState] = j;
prevPerson[newState] = i;
}
}
}
}
List<Integer> teamList = new ArrayList<Integer>();
int state = (1 << skills) - 1;
while (state > 0) {
teamList.add(prevPerson[state]);
state = prevState[state];
}
int teamSize = teamList.size();
int[] teamArray = new int[teamSize];
for (int i = 0; i < teamSize; i++)
teamArray[i] = teamList.get(teamSize - 1 - i);
return teamArray;
}
public int getMask(List<String> list, Map<String, Integer> map) {
int mask = 0;
for (String skill : list) {
if (map.containsKey(skill))
mask |= 1 << map.get(skill);
}
return mask;
}
}
```