Smallest Sufficient Team
Smallest Sufficient Team is a hard dynamic programming problem solved with the bitmask dp pattern.
The best approach, optimal (bitmask dp over skill sets), runs in O(2^m · p) time and O(2^m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from backtracking on the first missing skill up.
Problem
A project needs every skill in the list req_skills. You are also given people, where people[i] lists the skills that person i has. A team (a set of people, given by their indices) is sufficient when every required skill is held by at least one member.
Return a sufficient team with the fewest possible members, as a list of indices in any order. If several smallest teams exist, any one of them is accepted. A sufficient team is guaranteed to exist.
Examples
Example 1
- Input
req_skills = ["java", "sql", "git"], people = [["java"], ["sql", "git"], ["java", "git"], ["sql"]]- Output
[0, 1]- Why
- No single person knows all three skills, while person 0 (java) and person 1 (sql, git) together do. [1, 2] and [2, 3] are also accepted.
Example 2
- Input
req_skills = ["a", "b", "c", "d"], people = [["a", "b"], ["c"], ["b", "c", "d"], ["a"], ["d"]]- Output
[0, 2]- Why
- Person 2 covers b, c and d, and either person 0 or person 3 adds a. Three-person teams such as [0, 1, 4] work but are larger.
Constraints
1 <= req_skills.length <= 16; the skills are distinct lowercase words of length 1 to 16.1 <= people.length <= 600 <= people[i].length <= 16; every skill of a person is inreq_skills, with no repeats.- At least one team covering every required skill exists.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Backtracking on the first missing skill | O(p^m) worst case | O(m) |
| Optimal (bitmask DP over skill sets) | O(2^m · p) | O(2^m) |
1Backtracking on the first missing skill
O(p^m) worst caseEach level picks one of up to p people and covers at least one new skill, so the tree has depth at most m; pruning keeps it much smaller in practice.O(m)The recursion depth and the current team hold at most m entries.Map each skill to a bit and each person to a mask. Search recursively: find the lowest skill not covered yet, and try adding each person who has that skill. Any valid team must contain one of them, so no team is missed. Keep the best complete team and cut any branch that cannot be smaller than it.
- Build
skill -> bitandmask[p]for every person. dfs(covered, team): ifteam.size() >= best.size(), return. Ifcoveredis full, copyteamintobestand return.- Let
sbe the lowest bit missing fromcovered. For every personpwith bits: addp, recurse withcovered | mask[p], removep. - Start with
best= all people and return it as an array.
class Solution {
private int[] masks;
private int full;
private List<Integer> best;
public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
int m = reqSkills.length, n = people.size();
Map<String, Integer> bit = new HashMap<>();
for (int i = 0; i < m; i++) bit.put(reqSkills[i], i);
masks = new int[n];
for (int p = 0; p < n; p++)
for (String s : people.get(p)) masks[p] |= 1 << bit.get(s);
full = (1 << m) - 1;
best = new ArrayList<>();
for (int p = 0; p < n; p++) best.add(p);
dfs(0, new ArrayList<>());
return best.stream().mapToInt(Integer::intValue).toArray();
}
private void dfs(int covered, List<Integer> team) {
if (team.size() >= best.size()) return;
if (covered == full) {
best = new ArrayList<>(team);
return;
}
int need = Integer.numberOfTrailingZeros(~covered);
for (int p = 0; p < masks.length; p++) {
if ((masks[p] >> need & 1) == 0) continue;
team.add(p);
dfs(covered | masks[p], team);
team.remove(team.size() - 1);
}
}
}class Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
bit = {s: i for i, s in enumerate(req_skills)}
masks = []
for skills in people:
mask = 0
for s in skills:
mask |= 1 << bit[s]
masks.append(mask)
full = (1 << len(req_skills)) - 1
best = list(range(len(people)))
team = []
def dfs(covered: int) -> None:
nonlocal best
if len(team) >= len(best):
return
if covered == full:
best = team[:]
return
need = 0
while covered >> need & 1:
need += 1
for p, mask in enumerate(masks):
if mask >> need & 1:
team.append(p)
dfs(covered | mask)
team.pop()
dfs(0)
return bestclass Solution {
vector<int> masks, best;
int full;
void dfs(int covered, vector<int>& team) {
if (team.size() >= best.size()) return;
if (covered == full) {
best = team;
return;
}
int need = __builtin_ctz(~covered);
for (int p = 0; p < (int)masks.size(); p++) {
if (!(masks[p] >> need & 1)) continue;
team.push_back(p);
dfs(covered | masks[p], team);
team.pop_back();
}
}
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
int m = req_skills.size(), n = people.size();
unordered_map<string, int> bit;
for (int i = 0; i < m; i++) bit[req_skills[i]] = i;
masks.assign(n, 0);
for (int p = 0; p < n; p++)
for (auto& s : people[p]) masks[p] |= 1 << bit[s];
full = (1 << m) - 1;
best.clear();
for (int p = 0; p < n; p++) best.push_back(p);
vector<int> team;
dfs(0, team);
return best;
}
};function smallestSufficientTeam(req_skills, people) {
const bit = new Map(req_skills.map((s, i) => [s, i]));
const masks = people.map((skills) => skills.reduce((mask, s) => mask | (1 << bit.get(s)), 0));
const full = (1 << req_skills.length) - 1;
let best = people.map((_, i) => i);
const team = [];
const dfs = (covered) => {
if (team.length >= best.length) return;
if (covered === full) {
best = team.slice();
return;
}
let need = 0;
while ((covered >> need) & 1) need++;
for (let p = 0; p < masks.length; p++) {
if (((masks[p] >> need) & 1) === 0) continue;
team.push(p);
dfs(covered | masks[p]);
team.pop();
}
};
dfs(0);
return best;
}2Optimal (bitmask DP over skill sets)
O(2^m · p)Each of the 2^m masks is extended by each of the p people (65,536 x 60 at most).O(2^m)Three arrays indexed by mask.Let size[mask] be the fewest people whose combined skills are exactly mask, and remember for each mask the last person added and the mask before them. Adding a person only adds bits, so processing masks in increasing order finalizes each mask before it is extended. The team for the full mask is read back through the remembered links.
- Turn every person into a skill mask. Set
size[0] = 0and every other size to infinity. - For
maskfrom 0 tofull, skip it if unreachable; otherwise for each personpletnext = mask | skills[p]. Ifsize[mask] + 1 < size[next], setsize[next],prevMask[next] = maskandlastPerson[next] = p. - Starting at
full, repeatedly recordlastPerson[mask]and move toprevMask[mask]until reaching 0.
class Solution {
public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
int m = reqSkills.length, n = people.size();
Map<String, Integer> bit = new HashMap<>();
for (int i = 0; i < m; i++) bit.put(reqSkills[i], i);
int[] skills = new int[n];
for (int p = 0; p < n; p++)
for (String s : people.get(p)) skills[p] |= 1 << bit.get(s);
int full = (1 << m) - 1;
int[] size = new int[full + 1], prevMask = new int[full + 1], lastPerson = new int[full + 1];
Arrays.fill(size, Integer.MAX_VALUE);
size[0] = 0;
for (int mask = 0; mask <= full; mask++) {
if (size[mask] == Integer.MAX_VALUE) continue;
for (int p = 0; p < n; p++) {
int next = mask | skills[p];
if (size[mask] + 1 < size[next]) {
size[next] = size[mask] + 1;
prevMask[next] = mask;
lastPerson[next] = p;
}
}
}
int[] team = new int[size[full]];
for (int mask = full, i = 0; mask != 0; mask = prevMask[mask]) team[i++] = lastPerson[mask];
return team;
}
}class Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
bit = {s: i for i, s in enumerate(req_skills)}
skills = []
for person in people:
mask = 0
for s in person:
mask |= 1 << bit[s]
skills.append(mask)
full = (1 << len(req_skills)) - 1
INF = float("inf")
size = [INF] * (full + 1)
prev_mask = [0] * (full + 1)
last_person = [0] * (full + 1)
size[0] = 0
for mask in range(full + 1):
if size[mask] == INF:
continue
for p, sk in enumerate(skills):
nxt = mask | sk
if size[mask] + 1 < size[nxt]:
size[nxt] = size[mask] + 1
prev_mask[nxt] = mask
last_person[nxt] = p
team = []
mask = full
while mask:
team.append(last_person[mask])
mask = prev_mask[mask]
return teamclass Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
int m = req_skills.size(), n = people.size();
unordered_map<string, int> bit;
for (int i = 0; i < m; i++) bit[req_skills[i]] = i;
vector<int> skills(n, 0);
for (int p = 0; p < n; p++)
for (auto& s : people[p]) skills[p] |= 1 << bit[s];
int full = (1 << m) - 1;
vector<int> size(full + 1, INT_MAX), prevMask(full + 1, 0), lastPerson(full + 1, 0);
size[0] = 0;
for (int mask = 0; mask <= full; mask++) {
if (size[mask] == INT_MAX) continue;
for (int p = 0; p < n; p++) {
int next = mask | skills[p];
if (size[mask] + 1 < size[next]) {
size[next] = size[mask] + 1;
prevMask[next] = mask;
lastPerson[next] = p;
}
}
}
vector<int> team;
for (int mask = full; mask != 0; mask = prevMask[mask]) team.push_back(lastPerson[mask]);
return team;
}
};function smallestSufficientTeam(req_skills, people) {
const bit = new Map(req_skills.map((s, i) => [s, i]));
const skills = people.map((person) => person.reduce((mask, s) => mask | (1 << bit.get(s)), 0));
const full = (1 << req_skills.length) - 1;
const size = new Array(full + 1).fill(Infinity);
const prevMask = new Array(full + 1).fill(0);
const lastPerson = new Array(full + 1).fill(0);
size[0] = 0;
for (let mask = 0; mask <= full; mask++) {
if (size[mask] === Infinity) continue;
for (let p = 0; p < skills.length; p++) {
const next = mask | skills[p];
if (size[mask] + 1 < size[next]) {
size[next] = size[mask] + 1;
prevMask[next] = mask;
lastPerson[next] = p;
}
}
}
const team = [];
for (let mask = full; mask !== 0; mask = prevMask[mask]) team.push(lastPerson[mask]);
return team;
}Edge cases to test
- One person already has every skill
- People with no skills at all, or whose skills are a subset of someone else's
- Several different smallest teams (any one is accepted)
- Each skill held by exactly one person, so everyone with a unique skill must be chosen
Hints
Hint 1
With at most 16 skills, a set of skills fits in a 16-bit mask. Turn every person into a mask.
Hint 2
Backtracking: the first skill not yet covered must be supplied by someone, so branch only on the people who have it, and prune when the team cannot beat the best one found.
Hint 3
Dynamic programming over masks: let best[mask] be the smallest team whose skills are exactly mask. From each reachable mask, adding person p leads to mask | skills[p].
FAQ
What is the best time complexity for Smallest Sufficient Team?
Optimal (bitmask DP over skill sets) runs in O(2^m · p) time and O(2^m) extra space. Each of the 2^m masks is extended by each of the p people (65,536 x 60 at most).
Which pattern does Smallest Sufficient Team use?
It is a dynamic programming problem that uses the bitmask dp pattern. Other problems with the same pattern: Optimal Account Balancing, Frequencies of Shortest Supersequences, Minimum Number of Work Sessions to Finish the Tasks.
Is there a brute force solution for Smallest Sufficient Team?
Yes. Backtracking on the first missing skill takes O(p^m) worst case time and O(m) space. Map each skill to a bit and each person to a mask.
Which edge cases should I test for Smallest Sufficient Team?
One person already has every skill; People with no skills at all, or whose skills are a subset of someone else's; Several different smallest teams (any one is accepted); Each skill held by exactly one person, so everyone with a unique skill must be chosen.