Smallest Sufficient Team

Smallest Sufficient Team is a classic bitmask DP problem. The trick is to stop thinking about teams as lists of people and start thinking about them as a single integer: a bitmask where each bit says "this skill is covered." Once skills are bits, "smallest team that covers everything" becomes a tiny dynamic program over masks.

The slow way first

The brute force is to try every subset of people and check which subsets cover all skills, then keep the smallest. With up to 60 people that is 2^60 subsets — completely impossible.

The real question to ask: what actually matters about a team? Not which people are in it, but which skills it covers. With at most 16 required skills there are only 2^16 = 65536 possible "covered-skill" sets. That small number is the whole opening.

The idea: each skill is a bit

Number the skills 0, 1, 2, .... A set of covered skills is then a bitmask: bit k is 1 when skill k is covered. Person i becomes a mask too — the OR of their own skill bits.

Define dp[mask] = the smallest team whose covered skills equal exactly mask. Start with dp[0] = [] (the empty team covers nothing). Then for each person, OR their bits into every mask we can already reach: a team for had plus this person becomes a team for had | person. Keep whichever team is smaller. The answer is dp[full], where full is the all-ones mask.

Walk through it

Step through the animation. The three cells are the bits of the goal mask: reactjs, nodejs, java. We add people one at a time. Person 0 lights the java bit, person 1 the nodejs bit. Person 2 covers nodejs and reactjs at once, and ORed onto person 0's java mask it reaches 111 — all skills — giving the team [0, 2]. A longer path [0, 1, 2] also reaches 111, but it is size 3, so we keep the smaller [0, 2].

Pseudocode

map each skill to a bit index; full = all-ones mask
dp = { 0: [] }                       # empty team covers mask 0
for each person p with skill set "his" (as a mask):
    for each mask "had" already in dp:
        nm = had OR his              # new covered-skill set
        if nm unseen OR team(had)+1 is smaller than team(nm):
            dp[nm] = dp[had] + [p]   # better team for nm
return dp[full]

The Python solution

def smallest_team(req_skills, people):
    n = len(req_skills)
    idx = {s: i for i, s in enumerate(req_skills)}
    full = (1 << n) - 1
    dp = {0: []}
    for p, skills in enumerate(people):
        his = sum(1 << idx[s] for s in skills)
        for had in list(dp):
            nm = had | his
            if nm not in dp or len(dp[had]) + 1 < len(dp[nm]):
                dp[nm] = dp[had] + [p]
    return dp[full]

• idx maps each skill name to its bit position; full is the all-ones target mask.
• dp maps a covered-skill mask → the smallest team that achieves it. It starts with only dp[0] = [].
• his is person p as a mask: the OR of 1 << idx[s] over their skills.
• We snapshot list(dp) so we iterate the masks that existed before this person was added.
• nm = had | his is the new mask; if it is new or we found a smaller team, we record dp[had] + [p].
• dp[full] is the smallest team covering every skill.

Complexity

With S up to 16 skills, 2^S is about 65k — tiny. The number of people barely matters; what bounds us is the number of distinct skill masks, 2^S.

When this pattern shows up

Practice