Smallest Sufficient Team: Bitmask DP Pattern

You are given a list of required skills and a list of people, where each person has some subset of those skills. Your goal is to find the smallest team of people such that every required skill is covered by at least one team member. Return the indices of the chosen people.

This is LeetCode 1125: Smallest Sufficient Team, and it is a classic application of bitmask dynamic programming. The number of required skills is at most 16, which means you can represent any combination of skills as a single integer bitmask. That constraint is the green light for bitmask DP.

Why bitmasks?

The key observation is that skills are a set, and you care about which skills are covered, not the order. A bitmask is the most compact way to represent a set when the universe is small (16 or fewer elements). Each skill gets assigned a bit position. If a person knows skills at positions 1 and 2, their bitmask is 110 in binary, which is 6 in decimal.

When you add a person to your team, you OR their skill bitmask into your team's current coverage bitmask. The target is the bitmask with all bits set: (1 << n) - 1, where n is the number of required skills.

This turns a set-cover problem (which is NP-hard in general) into something tractable. With at most 16 skills, there are only 2^16 = 65,536 possible coverage states. That is small enough to enumerate.

The approach

Define dp[mask] as the smallest team (fewest people) that achieves exactly the skill coverage represented by mask. Initially, only dp[0] is reachable, with an empty team.

For each person, iterate over all currently reachable masks. For each reachable mask, compute new_mask = mask | person_skills. If new_mask has not been reached yet, or if the current team plus this person is smaller than whatever team was already stored at dp[new_mask], update it.

After processing all people, the answer is dp[(1 << n) - 1], the smallest team that covers every skill.

The solution

def smallest_sufficient_team(req_skills, people):
    n = len(req_skills)
    skill_index = {s: i for i, s in enumerate(req_skills)}
    target = (1 << n) - 1

    person_masks = []
    for person in people:
        mask = 0
        for skill in person:
            if skill in skill_index:
                mask |= 1 << skill_index[skill]
        person_masks.append(mask)

    dp = {0: []}

    for i, pmask in enumerate(person_masks):
        if pmask == 0:
            continue
        for mask, team in list(dp.items()):
            new_mask = mask | pmask
            if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:
                dp[new_mask] = team + [i]

    return dp[target]

The structure is clean. First, build a mapping from skill names to bit positions. Then convert each person's skill list into a bitmask. Finally, run the DP: for each person, try adding them to every reachable state and see if the resulting coverage improves on what was already recorded.

The list(dp.items()) call on line 14 is important. You need a snapshot of the current DP state before this person's updates start modifying it. Without the snapshot, you could add the same person multiple times in a single pass.

Skipping people with pmask == 0 is a minor optimization. A person with no relevant skills cannot improve any coverage, so there is no point iterating over the entire DP table for them.

Why this works

The DP explores all possible team compositions implicitly. Every reachable bitmask represents a distinct coverage state, and for each state, you keep only the smallest team that achieves it. When you process person i, you are asking: "for every coverage state I can already reach, what happens if I add this person?" If the new coverage state is reached for the first time, or reached with a smaller team than before, you update.

Because the bitmask captures the complete coverage information, you never lose track of which skills are still missing. And because you iterate over people in order and take a snapshot of dp.items() each time, each person is considered at most once per coverage state. The algorithm naturally finds the global minimum team.

Complexity analysis

Where m is the number of people and n is the number of required skills. The brute force tries all 2^m subsets of people, which is exponential in the number of people (up to 60). The bitmask DP is exponential only in the number of skills (at most 16), making it feasible. With m = 60 and n = 16, the DP does at most 60 * 65,536 = about 3.9 million iterations. That runs comfortably within time limits.

The space is O(2^n) for the DP table, with each entry storing a list of person indices (at most m entries in the worst case, but typically much smaller for the minimum team).

The building blocks

This problem combines two fundamental patterns:

• Bitmask state compression: when the universe of items is small (16 or fewer), represent subsets as integers. This converts set operations (union, intersection, membership) into bitwise operations (OR, AND, bit check). The same idea appears in Counting Bits, where bit manipulation drives the DP transitions.

• DP over subsets: define your state as a bitmask and transition by OR-ing in new elements. The DP table has 2^n entries, one per possible subset. This is the standard approach for set-cover and Hamiltonian-path style problems where n is small enough.

• Greedy team building with optimality tracking: at each step, you keep the best (smallest) team for each coverage state. This is the same "track the optimal solution at each state" idea that drives Coin Change, just with bitmasks instead of integer sums.

Edge cases to watch for

• A single person covers all skills: the answer is just that one person. The DP handles this naturally because OR-ing their mask with 0 gives the target immediately.
• People with no relevant skills: they contribute nothing. Skipping them with the pmask == 0 check avoids wasted work.
• Duplicate skill sets: two people with identical skills. The DP will pick whichever one it encounters first (or either one, since they are interchangeable). No special handling needed.
• All skills require different people: if no two skills share a person, the minimum team size equals the number of skills. The DP builds this up one person at a time.
• n = 1: only one required skill. The answer is any single person who has that skill. The DP finds this in the first pass.

From understanding to recall

The bitmask DP pattern is one of those techniques that feels magical the first time you see it, but becomes mechanical once you have practiced it a few times. The core idea is always the same: represent a set as an integer, transition by OR-ing in new elements, and iterate over all 2^n states.

What makes this problem a great drill is that it combines bitmask DP with solution tracking. You are not just computing a count or a boolean. You are reconstructing the actual team. That extra bookkeeping (storing the team list at each DP state) is a skill that transfers to many other problems where you need to recover the optimal solution, not just its cost.

Spacing your practice over days and weeks is what moves this from "I understand the idea" to "I can write it from scratch in an interview."

Related posts

• Counting Bits - Uses bit manipulation to build a DP table where each entry depends on a right-shifted predecessor. Same family of bitwise DP thinking.
• Coin Change - Classic DP where you track the optimal value at each state. Same structure of "for each item, update all reachable states," but with integer sums instead of bitmasks.
• Combinations - Generating subsets via backtracking. Smallest Sufficient Team is essentially searching through subsets of people, but bitmask DP makes it tractable where brute-force enumeration would not.