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 ith 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
andpeople[i]
are (respectively) distinct. req_skills[i][j], people[i][j][k]
are lowercase English letters. Every skill in
people[i]
is a skill inreq_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
, thendp[state][j + 1] = dp[state][j]
 Pick people
j
, thendp[state][j + 1] = dp[prevState][j] + 1
, whereprevState
isstate
subtracting all the skills peoplej
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 peoplej
.  Otherwise, we should pick people
j
. So we pushj
into the answer, and subtract the skills peoplej
has from thestate
.
We loop until state == 0
.
// OJ: https://leetcode.com/problems/smallestsufficientteam/
// 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/smallestsufficientteam/
// 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/smallestsufficientteam/
// 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/smallestsufficientteam/discuss/342120/C%2B%2BDP32msDPsolution.Easytoimplement
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; } }

Todo

print("Todo!")