In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the person has.
Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.
team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.
It is guaranteed an answer exists.
Example 1:
Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] Output: [0,2]
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]
Constraints:
1 <= req_skills.length <= 161 <= req_skills[i].length <= 16req_skills[i] consists of lowercase English letters.req_skills are unique.1 <= people.length <= 600 <= people[i].length <= 161 <= people[i][j].length <= 16people[i][j] consists of lowercase English letters.people[i] are unique.people[i] is a skill in req_skills.Problem Overview: Given a list of required skills and a list of people with subsets of those skills, find the smallest group of people whose combined skills cover every requirement. The output is the indices of people forming that minimum team.
Approach 1: Backtracking (Exponential)
This approach tries every combination of people and checks whether their combined skills cover all required skills. Represent each person's skills as a bitmask, then recursively decide whether to include or skip each person. During recursion, maintain the current skill mask and the team members selected so far. If the mask covers all skills, update the best solution if the team is smaller. Time complexity is O(2^n * m) where n is the number of people and m is the number of skills, since every subset may be explored and skill masks are merged using bit operations. Space complexity is O(n) due to recursion depth and temporary team storage. This method demonstrates the brute-force search space but becomes impractical as the number of people grows.
Approach 2: Bitmask with Dynamic Programming (O(n · 2^m))
The optimized approach encodes each skill as a bit position and represents a person's skills using a bitmask. The goal becomes covering the full skill mask (1 << m) - 1. Use dynamic programming where the key is a skill mask and the value is the smallest team that achieves it. Start with dp[0] = []. For each person, compute their skill mask and iterate over existing DP states. Combine the current mask with the person's mask using bitwise OR. If this new mask can be achieved with fewer people than previously recorded, update the DP entry with the new team. Because there are at most 2^m skill states and each person updates them once, the time complexity is O(n · 2^m) and space complexity is O(2^m). Bit operations make state transitions extremely fast.
This solution relies heavily on bit manipulation and bitmask representations. Skills are compressed into integers, allowing union operations using a single OR instruction. The DP map effectively tracks the smallest team for every possible skill combination, ensuring the final result is minimal.
Recommended for interviews: The Bitmask Dynamic Programming approach is what interviewers typically expect. It shows you understand state compression and how to model subset coverage efficiently. Backtracking demonstrates the brute-force reasoning, but recognizing the small skill limit and converting the problem into a 2^m DP is the key insight that signals strong problem-solving ability.
This approach leverages a bitmask along with dynamic programming to solve the problem of finding the smallest sufficient team. We use a bitmask to represent the combination of skills possessed by a team. Dynamic programming is employed to track the smallest team for every possible combination of skills, allowing us to build up to a team that covers all required skills.
The code utilizes a dictionary, skill_index, to map each skill to a unique index. We then define a dynamic programming dictionary, dp, where each key represents a set of skills (using bitmask), and value is the team of indices representing people with these skills.
For each person, we calculate the his_skill bitmask, which marks the skills this person can cover. We iterate over each entry in our dynamic programming table, updating it with the new combinations of skills that could be formed by adding the current person.
The result is found in dp[(1 << n) - 1], where n is the length of req_skills, representing the full set of skills covered.
Python
C++
JavaScript
Time Complexity: O(people.length * 2^n), where n is the number of required skills. Space Complexity: O(2^n).
This approach utilizes backtracking to explore all possible combinations of people in attempting to form the smallest team covering all required skills. We prune branches once we find a valid team, retaining the best (smallest) solution observed so far.
This Java implementation uses recursion to explore the assembly of teams in a backtracking manner. We map each skill to a bit index, then convert each person's skills to a bitmask. We recursively decide whether to include each person in the current team, pruning branches that exceed the current smallest team's size or cannot complete the skill set. The smallest sufficient team is stored in bestTeam.
Time Complexity: O(2^people.length), worst case exploring all combinations. Space Complexity: O(people.length) due to recursive depth.
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.
First, we map each skill in req_skills to a number, i.e., d[s] represents the number of skill s. Then, we traverse each person in people and represent the skills they master with a binary number, i.e., p[i] represents the skills mastered by the person with number i.
Next, we define the following three arrays:
f[i] represents the minimum number of people to master the skill set i, where each bit of the binary representation of i is 1, indicating that the corresponding skill is mastered. Initially, f[0] = 0, and all other positions are infinity.g[i] represents the number of the last person when the skill set i is mastered by the minimum number of people.h[i] represents the previous skill set state when the skill set i is mastered by the minimum number of people.We enumerate each skill set in the range of [0,..2^m-1], for each skill set i:
We enumerate each person j in people. If f[i] + 1 \lt f[i | p[j]], it means that f[i | p[j]] can be transferred from f[i]. At this time, we update f[i | p[j]] to f[i] + 1, and update g[i | p[j]] to j, and update h[i | p[j]] to i. That is, when the current skill set state is i | p[j], the number of the last person is j, and the previous skill set state is i. Here, the symbol | represents bitwise OR operation.
Finally, we start from the skill set i=2^m-1, find the number of the last person at this time g[i], add it to the answer, then update i to h[i], and keep backtracking until i=0, to get the personnel numbers in the smallest necessary team.
The time complexity is O(2^m times n), and the space complexity is O(2^m). Here, m and n are the lengths of req_skills and people, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Bitmask with Dynamic Programming | Time Complexity: O(people.length * 2^n), where n is the number of required skills. Space Complexity: O(2^n). |
| Backtracking | Time Complexity: O(2^people.length), worst case exploring all combinations. Space Complexity: O(people.length) due to recursive depth. |
| State Compression Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^n * m) | O(n) | Conceptual brute force for small inputs or when demonstrating subset exploration |
| Bitmask Dynamic Programming | O(n · 2^m) | O(2^m) | Optimal solution when the number of required skills is small (≤16) |
Smallest Sufficient Team II DP II Bit Manipulation II 0/1 Knapsack II Leetcode 1125 • Aryan Mittal • 7,264 views views
Watch 9 more video solutions →Practice Smallest Sufficient Team with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor