HardArrayDynamic ProgrammingBit ManipulationBitmaskUpdated Sep 2026

1125. Smallest Sufficient Team

Asked at Airbnb

Difficulty

Hard

Time

O(2^m * n)

Space

O(2^m)

Pattern

Array

Companies

1

Problem

You are given a list of required skills req_skills and a list of people. Person i knows the skills listed in people[i].

A team is sufficient if every required skill is known by at least one member of the team. Return the smallest sufficient team, written as the list of person indices. If several teams have the same smallest size, any one of them is accepted.

There are at most 16 required skills, so a skill set fits in a small bitmask. There are up to 60 people, so trying every subset of people is far too slow. The trick is to do dynamic programming over skill masks instead of over people.

Cover all required skills with fewest people

req_skillsjavanodejsreactjs012Three skills must all be covered.people012javanodejsnodejsreactjsPerson 0 has java, person 1 has nodejs, person 2 hasnodejs and reactjs.team [0,2] covers java + nodejs + reactjssize 2 — no single person covers all three
Each person is a small set of skills; we need the smallest group whose sets together cover every required skill.

Constraints

  • ●1 <= req_skills.length <= 16
  • ●1 <= req_skills[i].length <= 16
  • ●req_skills[i] consists of lowercase English letters
  • ●All strings in req_skills are unique
  • ●1 <= people.length <= 60
  • ●0 <= people[i].length <= 16
  • ●1 <= people[i][j].length <= 16
  • ●people[i][j] consists of lowercase English letters

Examples

Example 1
Inputreq_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output[0,2]
WhyPerson 0 covers java, person 2 covers nodejs and reactjs. Together they cover all three skills with only 2 people. Any team of size 1 fails: no single person knows all three skills.
Example 2
Inputreq_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"
Output[1,2]
WhyPerson 1 covers algorithms, math and reactjs. Person 2 covers java, csharp and aws. Those two people together cover all six required skills, and no single person covers everything.

Asked At

1 companies
CompanyDifficulty
AirbnbHardView all Airbnb questions →

How to Think About It

1

Trying all subsets of people is 2^60 — impossible. But there are only 2^16 = 65536 possible skill sets, so DP over skill sets instead.

2

Encode each person's skills as a bitmask using an index map from skill name to bit.

3

Key insight: dp[mask] = size of the smallest team whose combined skills are exactly mask. From each reachable mask, adding person i reaches mask | skills[i] with one more member.

4

Store how you reached each mask (the person added and the previous mask) so you can reconstruct the team at the end.

5

Iterating masks in increasing order works because mask | skills[i] >= mask, so every state is final before it is expanded.

Optimal Approach

Step 1: Map skills to bits; compute pm[i] for each person.
Step 2: dp[0] = 0, all other dp = inf; arrays parent and who.
Step 3: For mask from 0 to 2^m - 1 (skip if dp[mask] is inf):
For each person i: nm = mask | pm[i]; if dp[mask] + 1 < dp[nm]: set dp[nm], parent[nm] = mask, who[nm] = i.
Step 4: Walk back from the full mask via parent, collecting who.

Time: O(2^m * n). Space: O(2^m).

DP over skill masks

dp00000101001110010111011101121223Start at mask 000 with size 0; the goal is mask 111.mask 000 + person 0 → 001, size 1mask 000 + person 2 → 110, size 1mask 001 + person 2 → 111, size 2From each reachable mask, try every person and keep thecheapest way to reach the new mask.dp[mask | pm[i]] = min(dp[mask | pm[i]], dp[mask] + 1)parent[nm] = mask, who[nm] = i
dp[mask] is the smallest team size that covers exactly the skills in mask; adding a person ORs in their bits.
ComplexityTime O(2^m * n)Space O(2^m)m is the number of required skills (at most 16) and n is the number of people; every reachable skill mask is expanded once against every person.

What Trips People Up in Real Interviews

1

Enumerating subsets of people. The constraint to exploit is the tiny number of skills.

2

Storing whole team lists in every DP cell. It works but copies lists constantly; parent pointers are leaner.

3

Forgetting that a person with no required skills never helps — they are naturally skipped because mask | 0 == mask.

4

Not explaining why increasing mask order is valid.

Solution Code

O(2^m * n) time
def smallestSufficientTeam(req_skills, people):
    m = len(req_skills)
    bit = {s: i for i, s in enumerate(req_skills)}
    pm = []
    for p in people:
        mask = 0
        for s in p:
            mask |= 1 << bit[s]
        pm.append(mask)
    full = (1 << m) - 1
    INF = float('inf')
    dp = [INF] * (1 << m)
    parent = [-1] * (1 << m)
    who = [-1] * (1 << m)
    dp[0] = 0
    for mask in range(1 << m):
        if dp[mask] == INF:
            continue
        for i, p in enumerate(pm):
            nm = mask | p
            if dp[mask] + 1 < dp[nm]:
                dp[nm] = dp[mask] + 1
                parent[nm] = mask
                who[nm] = i
    team = []
    mask = full
    while mask:
        team.append(who[mask])
        mask = parent[mask]
    return team

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Smallest Sufficient Team problem?

Smallest Sufficient Team gives you a list of required skills (at most 16) and people with subsets of those skills, and asks for the smallest team that covers every required skill. The small skill count is the hint: represent skill sets as bitmasks and run a DP over all `2^16` masks.

How do you solve Smallest Sufficient Team?

The optimal approach runs in O(2^m * n) time and O(2^m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Smallest Sufficient Team?

Smallest Sufficient Team is asked at Airbnb. It is a hard difficulty problem.

What are common mistakes on Smallest Sufficient Team?
  • Enumerating subsets of people. The constraint to exploit is the tiny number of skills.
  • Storing whole team lists in every DP cell. It works but copies lists constantly; parent pointers are leaner.
  • Forgetting that a person with no required skills never helps — they are naturally skipped because `mask | 0 == mask`.
  • Not explaining why increasing mask order is valid.