Skip to main content
Talentd

Smallest Sufficient Team - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationBitmask20 min readAsked at: TCS
Practice this problem

Problem Statement

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.

  • For example, 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 <= 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.

Approach Overview

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.

Approach 1: Bitmask with Dynamic Programming

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.

Code

PythonC++JavaScript

Python

C++

JavaScript

Complexity

Time Complexity: O(people.length * 2^n), where n is the number of required skills. Space Complexity: O(2^n).

Try this approach in the editor →

Approach 2: Backtracking

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.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(2^people.length), worst case exploring all combinations. Space Complexity: O(people.length) due to recursive depth.

Try this approach in the editor →

Approach 3: 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.

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:

  • Array 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.
  • Array g[i] represents the number of the last person when the skill set i is mastered by the minimum number of people.
  • Array 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BacktrackingO(2^n * m)O(n)Conceptual brute force for small inputs or when demonstrating subset exploration
Bitmask Dynamic ProgrammingO(n · 2^m)O(2^m)Optimal solution when the number of required skills is small (≤16)

Video Solution

Smallest Sufficient Team | Recur + Memo | Bit Manipulation Made Easy | AMAZON | Leetcode-1125 • codestorywithMIK • 7,936 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Sufficient Team easy or hard?
Smallest Sufficient Team is categorized as a Hard problem on LeetCode. The challenge comes from recognizing that the number of skills is small and using bitmask dynamic programming to compress the state space instead of exploring all subsets of people.
Smallest Sufficient Team Python/Java solution
Most implementations follow the bitmask DP pattern. Python typically uses dictionaries mapping masks to lists of people, while Java often uses HashMap<Integer, List<Integer>>. The algorithm iterates through people, updates skill masks with bitwise OR, and keeps the smallest team for each state.
How to solve Smallest Sufficient Team in O(n · 2^m)?
Convert each required skill into a bit index and represent every person's skills as a bitmask. Maintain a DP map where keys are skill masks and values are the smallest teams achieving those masks. For each person, combine their mask with existing states using bitwise OR and update the team if it becomes smaller.
What is the best approach for Smallest Sufficient Team?
The most efficient solution uses bitmask dynamic programming. Each skill is mapped to a bit position and every person's skills are stored as a bitmask. DP tracks the smallest team for each skill combination. This reduces the search space to 2^m states where m is the number of skills, giving a time complexity of O(n · 2^m).
Is Smallest Sufficient Team asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests state compression, dynamic programming, and bit manipulation. Interviewers use it to evaluate whether candidates can reduce a combinatorial search into a manageable DP over bitmasks.
What data structure is used in Smallest Sufficient Team?
The main structures are bitmasks and a hash map or dictionary used for dynamic programming states. Each key represents a combination of skills, while the value stores the indices of people forming the smallest team for that combination.
What is the time complexity of Smallest Sufficient Team?
The optimal bitmask DP solution runs in O(n · 2^m) time, where n is the number of people and m is the number of required skills. Since m is usually limited to around 16, the number of possible skill states is manageable. Space complexity is O(2^m) for storing the best team for each skill mask.

Ready to solve this problem?

Practice Smallest Sufficient Team with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Rows Covered by Columns

Next

Minimum Number of Work Sessions to Finish the Tasks