#1125

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Smallest Sufficient Team

Find the smallest subset of people covering all required skills using bitmask dynamic programming for efficient state transitions.

array dynamic programming bit manipulation bitmask

Problem Statement

You are given a list of required skills req_skills and a list of people where each person has a subset of these skills. Your goal is to form a team such that every skill in req_skills is possessed by at least one person in the team.

Return any team of the smallest possible size represented by indices of people. The solution must handle overlapping skills efficiently and can be returned in any order.

Examples

Example 1

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]

Output: [0,2]

Example details omitted.

Example 2

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]

Output: [1,2]

Example details omitted.

Constraints

1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] consists of lowercase English letters.
All the strings of 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.
All the strings of people[i] are unique.
Every skill in people[i] is a skill in req_skills.
It is guaranteed a sufficient team exists.

Solution Approach

Bitmask Representation

Map each skill in req_skills to a unique bit in an integer. Each person's skill set can then be represented as a bitmask, allowing fast combination of multiple people using bitwise OR operations.

Dynamic Programming State Transitions

Use a DP array where each index represents a bitmask of skills covered. Iterate over people and update DP states by adding the person's skills to existing states. Keep track of the smallest team for each bitmask.

Reconstruct the Team

After computing DP for all skill combinations, backtrack from the full skill bitmask to extract the indices of people forming the minimal sufficient team. Handle ties arbitrarily since any smallest team is valid.

Complexity Analysis

Metric	Value
Time	O(2^m \cdot n)
Space	O(2^m)

Time complexity is O(2^m * n) where m is the number of skills and n is the number of people, as each DP state can be updated for each person. Space complexity is O(2^m) for storing minimal teams per skill subset.

What Interviewers Usually Probe

Expecting an efficient solution using bitmask DP rather than brute-force subsets.
Looking for handling of overlapping skills and minimizing team size simultaneously.
Interested in correct reconstruction of team indices from DP states.

Common Pitfalls or Variants

Common pitfalls

Not mapping skills consistently to bits, leading to incorrect DP updates.
Overwriting DP states without checking if the new team is smaller.
Failing to backtrack properly to recover team indices.

Follow-up variants

Return the number of people in the smallest sufficient team instead of indices.
Find all possible smallest sufficient teams covering all skills.
Optimize for additional constraints like skill priorities or maximum team size.

FAQ

What is the main strategy for solving Smallest Sufficient Team?

The key is bitmask dynamic programming, where each skill subset is represented as a bitmask and DP tracks minimal teams for each subset.

How do I handle overlapping skills among people?

Combine skill bitmasks using bitwise OR and update DP only if the new team is smaller, ensuring efficient coverage without redundant members.

Can the solution return any smallest team?

Yes, multiple minimal teams can exist, and any valid one can be returned as long as all skills are covered.

What is the time complexity for this problem?

It is O(2^m * n), where m is the number of skills and n is the number of people, due to iterating over all skill subsets for each person.

Is backtracking needed after DP?

Yes, backtracking from the full skill bitmask is required to extract the indices of people forming the minimal sufficient team.

terminal

Solution

Solution 1: State Compression Dynamic Programming

We notice that the length of `req_skills` does not exceed $16$, so we can use a binary number of length no more than $16$ to represent whether each skill is mastered. Let's denote the length of `req_skills` as $m$ and the length of `people` as $n$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def smallestSufficientTeam(
        self, req_skills: List[str], people: List[List[str]]
    ) -> List[int]:
        d = {s: i for i, s in enumerate(req_skills)}
        m, n = len(req_skills), len(people)
        p = [0] * n
        for i, ss in enumerate(people):
            for s in ss:
                p[i] |= 1 << d[s]
        f = [inf] * (1 << m)
        g = [0] * (1 << m)
        h = [0] * (1 << m)
        f[0] = 0
        for i in range(1 << m):
            if f[i] == inf:
                continue
            for j in range(n):
                if f[i] + 1 < f[i | p[j]]:
                    f[i | p[j]] = f[i] + 1
                    g[i | p[j]] = j
                    h[i | p[j]] = i
        i = (1 << m) - 1
        ans = []
        while i:
            ans.append(g[i])
            i = h[i]
        return ans

Continue Practicing

#996 number of squareful arrays #1255 maximum score words formed by letters #943 find the shortest superstring