Smallest Sufficient Team

Hard Dynamic Programming Bitmask DP Original on LeetCode

Reported atAirbnb

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 <= 60
  • 0 <= people[i].length <= 16; every skill of a person is in req_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.

00:00
Testcase

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.

ApproachTimeSpace
Backtracking on the first missing skillO(p^m) worst caseO(m)
Optimal (bitmask DP over skill sets)O(2^m · p)O(2^m)

1Backtracking on the first missing skill

TimeO(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.
SpaceO(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.

  1. Build skill -> bit and mask[p] for every person.
  2. dfs(covered, team): if team.size() >= best.size(), return. If covered is full, copy team into best and return.
  3. Let s be the lowest bit missing from covered. For every person p with bit s: add p, recurse with covered | mask[p], remove p.
  4. 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);
        }
    }
}

2Optimal (bitmask DP over skill sets)

TimeO(2^m · p)Each of the 2^m masks is extended by each of the p people (65,536 x 60 at most).
SpaceO(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.

  1. Turn every person into a skill mask. Set size[0] = 0 and every other size to infinity.
  2. For mask from 0 to full, skip it if unreachable; otherwise for each person p let next = mask | skills[p]. If size[mask] + 1 < size[next], set size[next], prevMask[next] = mask and lastPerson[next] = p.
  3. Starting at full, repeatedly record lastPerson[mask] and move to prevMask[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;
    }
}

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.