# Smallest Sufficient Team
**Difficulty:** HARD
[External](https://leetcode.com/problems/smallest-sufficient-team)
Canonical: https://scaleengineer.com/dsa/problems/smallest-sufficient-team
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## Problem
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.

# Approaches
## Backtracking Search
This approach attempts to solve the problem by generating all possible subsets of people and checking each subset for two conditions: whether it covers all the required skills and whether it is the smallest such subset found so far. This is a brute-force method that uses recursion and backtracking to navigate the search space of all possible teams.
**Time:** O(2^m * m). The algorithm explores `2^m` subsets of people. For each valid subset, it takes O(m) to construct and check. · **Space:** O(m), where `m` is the number of people. This space is used for the recursion stack and to store the current team being built.
**Pros:** Conceptually simple and easy to understand.; A natural starting point for subset-related problems.
**Cons:** Extremely inefficient due to its exponential time complexity with respect to the number of people.; Will result in a 'Time Limit Exceeded' error for the constraints of this problem.
### Explanation
The backtracking algorithm systematically generates all combinations of people. It uses a recursive function that, for each person, decides whether to include them in the team or not. This creates a search tree where each path from the root to a leaf represents a potential team.

We maintain a bitmask to keep track of the skills covered by the team being built. A bitmask is an integer where the `i`-th bit is set if the `i`-th required skill is covered. The target is a mask where all bits corresponding to required skills are set.

To make this feasible for very small inputs, we must use pruning. If at any point the size of the team we are currently building becomes equal to or larger than the size of the best solution we've already found, we can abandon that path of exploration (prune the search tree). However, since the number of people can be up to 60, the number of subsets is `2^60`, which is far too large to explore even with pruning.

```java
class Solution {
    List<Integer> smallestTeam = new ArrayList<>();
    int[] pSkills;
    int n, m;
    int targetMask;

    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        n = req_skills.length;
        m = people.size();
        targetMask = (1 << n) - 1;
        
        Map<String, Integer> skillMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            skillMap.put(req_skills[i], i);
        }

        pSkills = new int[m];
        for (int i = 0; i < m; i++) {
            for (String skill : people.get(i)) {
                pSkills[i] |= (1 << skillMap.get(skill));
            }
        }

        for (int i = 0; i < m; i++) smallestTeam.add(i); // Initialize with a team of all people

        backtrack(0, new ArrayList<>(), 0);

        int[] result = new int[smallestTeam.size()];
        for (int i = 0; i < smallestTeam.size(); i++) {
            result[i] = smallestTeam.get(i);
        }
        return result;
    }

    private void backtrack(int p_idx, List<Integer> currentTeam, int mask) {
        if (mask == targetMask) {
            if (currentTeam.size() < smallestTeam.size()) {
                smallestTeam = new ArrayList<>(currentTeam);
            }
            return;
        }

        if (p_idx == m || currentTeam.size() >= smallestTeam.size()) {
            return;
        }

        // Exclude person p_idx
        backtrack(p_idx + 1, currentTeam, mask);

        // Include person p_idx
        currentTeam.add(p_idx);
        backtrack(p_idx + 1, currentTeam, mask | pSkills[p_idx]);
        currentTeam.remove(currentTeam.size() - 1);
    }
}
```
### Algorithm
- The core idea is to explore all possible subsets of people.
- A recursive function, say `backtrack(index, current_team, current_mask)`, is used.
- `index` is the index of the person to consider.
- `current_team` is the list of people indices chosen so far.
- `current_mask` is a bitmask of the skills covered by the `current_team`.
- **Base Case:** When `index` reaches the end of the people list, if `current_mask` covers all required skills, we compare `current_team`'s size with the best solution found so far and update if it's smaller.
- **Recursive Step:** For the person at `index`, we make two recursive calls:
  1.  **Exclude:** `backtrack(index + 1, current_team, current_mask)`.
  2.  **Include:** Add the person to `current_team`, update `current_mask`, and call `backtrack(index + 1, ...)`.
- **Pruning:** An important optimization is to stop exploring a branch if the `current_team` size is already greater than or equal to the smallest team found so far.

## Dynamic Programming with Bitmask
This approach utilizes dynamic programming with bitmasking, which is well-suited for this problem due to the small number of required skills (`n <= 16`). The state of our DP is the set of skills covered, represented by a bitmask. We build up a solution for covering more skills by iteratively adding one person at a time and updating the smallest team for the newly covered skill sets.
**Time:** O(m * 2^n * k), where `m` is the number of people, `n` is the number of skills, and `k` is the max team size. The `k` factor comes from copying lists. · **Space:** O(2^n * k), where `n` is the number of skills and `k` is the max team size. The DP table stores `2^n` lists, each potentially of size up to `k`.
**Pros:** Guaranteed to find the optimal solution.; Feasible for the given constraints on the number of skills (`n`).; More efficient than brute-force backtracking.
**Cons:** High memory usage because a list of people is stored for each of the `2^n` DP states.; Copying lists during DP updates is time-consuming, adding a factor of the team size to the time complexity.
### Explanation
The key insight is to use the set of acquired skills as the DP state. Since there are at most 16 skills, we can represent any subset of skills with a 16-bit integer, or a bitmask. Let `dp[mask]` be the smallest team (represented as a list of people indices) that collectively has the skills represented by `mask`.

The DP table `dp` will have `2^n` entries. We initialize `dp[0]` as an empty team. Then, we process each person one by one. For each person `p` with skills `p_skills`, we can potentially improve the teams for various skill masks. We iterate through all masks `j` for which we already have a solution `dp[j]`. By adding person `p` to the team `dp[j]`, we get a new team that covers skills `j | p_skills`. If this new team is smaller than any previously found team for `j | p_skills`, we update `dp[j | p_skills]`.

An important detail is to iterate the masks `j` in decreasing order. This ensures that when we consider person `p`, all updates are based on teams formed by people before `p`, preventing person `p` from being used to update a state that is then used again in the same iteration.

As a practical optimization, we can pre-process the list of people to remove any person whose skill set is a strict subset of another person's skill set. This can reduce `m`, the number of people, and speed up the computation, though it doesn't change the worst-case complexity.

```java
class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        int m = people.size();
        Map<String, Integer> skillMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            skillMap.put(req_skills[i], i);
        }

        List<Integer>[] dp = new List[1 << n];
        dp[0] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int pSkill = 0;
            for (String skill : people.get(i)) {
                pSkill |= (1 << skillMap.get(skill));
            }

            for (int j = (1 << n) - 1; j >= 0; j--) {
                if (dp[j] == null) continue;

                int nextMask = j | pSkill;
                if (dp[nextMask] == null || dp[j].size() + 1 < dp[nextMask].size()) {
                    List<Integer> newTeam = new ArrayList<>(dp[j]);
                    newTeam.add(i);
                    dp[nextMask] = newTeam;
                }
            }
        }

        List<Integer> resList = dp[(1 << n) - 1];
        return resList.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
- First, map each skill to a unique index from `0` to `n-1` to enable bitmasking.
- Compute a skill bitmask for each person.
- Create a DP table, `dp`, of size `2^n`, where `dp[mask]` will store the list of people forming the smallest team for the skills in `mask`.
- Initialize `dp[0]` to an empty list. All other entries are `null`.
- Iterate through each person `p` from `0` to `m-1`.
- For each person, iterate through all existing skill masks `j` from `(1 << n) - 1` down to `0`.
- If `dp[j]` is not `null` (meaning a team for mask `j` exists), calculate `next_mask = j | p_skills[p]`.
- If no team exists for `next_mask` yet, or if the new team (`dp[j].size() + 1`) is smaller than the existing team for `next_mask`, update `dp[next_mask]` by creating a copy of `dp[j]` and adding person `p`.
- The final answer is the list stored in `dp[(1 << n) - 1]`.

## Optimized Dynamic Programming with Path Reconstruction
This approach is a highly optimized version of the dynamic programming solution. Instead of storing the full list of team members at each DP state, which is costly in terms of both time (for copying) and space, we only store the size of the team. To recover the actual team members, we use auxiliary arrays to keep track of how each optimal state was reached. This allows us to reconstruct the final team after the DP computation is complete.
**Time:** O(m * 2^n), where `m` is the number of people and `n` is the number of skills. This is a significant improvement over the non-optimized DP approach. · **Space:** O(2^n), where `n` is the number of skills. We need space for the `dp` array and the two parent-pointer arrays.
**Pros:** This is the most efficient approach for the given constraints.; Avoids costly list copying, leading to a much better time complexity.; Reduces space complexity by not storing full teams in the DP table.
**Cons:** The implementation is slightly more complex due to the need for a separate path reconstruction step after filling the DP table.
### Explanation
The core logic remains the same as the previous DP approach, but we optimize the data storage. The DP state `dp[mask]` now only stores an integer representing the minimum team size for covering the skills in `mask`.

To be able to find the actual team members, we need to record the choice that led to each optimal value. We use two helper arrays: `parent_person[mask]` stores the index of the last person added to form the optimal team for `mask`, and `parent_mask[mask]` stores the skill mask that the team had *before* this last person was added.

The DP transition is: when considering person `p` and a previous state `j`, if adding `p` creates a smaller team for `next_mask = j | p_skills[p]`, we update `dp[next_mask]` with the new smaller size and record `p` and `j` as the parents of this new state.

Once the DP table is fully populated, we can find the members of the smallest sufficient team by starting at the target mask `(1 << n) - 1`. We add `parent_person[(1 << n) - 1]` to our result team, then move to the state `parent_mask[(1 << n) - 1]`, and repeat this process until we trace our way back to the initial mask `0`.

This avoids the expensive list copying operations within the main DP loops, significantly improving performance.

```java
class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        int m = people.size();
        Map<String, Integer> skillMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            skillMap.put(req_skills[i], i);
        }

        int[] pSkills = new int[m];
        for (int i = 0; i < m; i++) {
            for (String skill : people.get(i)) {
                pSkills[i] |= (1 << skillMap.get(skill));
            }
        }

        int[] dp = new int[1 << n];
        Arrays.fill(dp, m + 1);
        dp[0] = 0;
        int[] parent_mask = new int[1 << n];
        int[] parent_person = new int[1 << n];

        for (int i = 0; i < m; i++) {
            if (pSkills[i] == 0) continue;
            for (int j = (1 << n) - 1; j >= 0; j--) {
                if (dp[j] >= m) continue;
                int nextMask = j | pSkills[i];
                if (dp[j] + 1 < dp[nextMask]) {
                    dp[nextMask] = dp[j] + 1;
                    parent_mask[nextMask] = j;
                    parent_person[nextMask] = i;
                }
            }
        }

        List<Integer> res = new ArrayList<>();
        int currentMask = (1 << n) - 1;
        while (currentMask != 0) {
            res.add(parent_person[currentMask]);
            currentMask = parent_mask[currentMask];
        }
        return res.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
- Map skills to indices and compute person skill masks, just like in the previous approach.
- Create a DP array `dp` of size `2^n` to store the *size* of the smallest team for each mask. Initialize `dp[0] = 0` and all other entries to a value larger than `m` (infinity).
- Create two additional arrays, `parent_mask` and `parent_person`, both of size `2^n`, to store pointers for reconstructing the solution path.
- Iterate through each person `p` and then through all masks `j` from `(1 << n) - 1` down to `0`.
- For each state `j`, calculate the `next_mask = j | p_skills[p]`.
- If `dp[j] + 1 < dp[next_mask]`, it means we've found a smaller team for `next_mask`. Update `dp[next_mask] = dp[j] + 1`, and store the backtracking information: `parent_mask[next_mask] = j` and `parent_person[next_mask] = p`.
- After the loops complete, `dp[(1 << n) - 1]` holds the size of the smallest team.
- Reconstruct the team by starting from the final mask `(1 << n) - 1` and following the `parent_mask` and `parent_person` pointers back to mask `0`, collecting the person indices along the way.

# Solutions
### Java

```java
class Solution { public int [] smallestSufficientTeam ( String [] req_skills , List < List < String >> people ) { Map < String , Integer > d = new HashMap <>(); int m = req_skills . length ; int n = people . size (); for ( int i = 0 ; i < m ; ++ i ) { d . put ( req_skills [ i ], i ); } int [] p = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { for ( var s : people . get ( i )) { p [ i ] |= 1 << d . get ( s ); } } int [] f = new int [ 1 << m ]; int [] g = new int [ 1 << m ]; int [] h = new int [ 1 << m ]; final int inf = 1 << 30 ; Arrays . fill ( f , inf ); f [ 0 ] = 0 ; for ( int i = 0 ; i < 1 << m ; ++ i ) { if ( f [ i ] == inf ) { continue ; } for ( int j = 0 ; j < n ; ++ j ) { 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 ; } } } List < Integer > ans = new ArrayList <>(); for ( int i = ( 1 << m ) - 1 ; i != 0 ; i = h [ i ]) { ans . add ( g [ i ]); } return ans . stream (). mapToInt ( Integer: : intValue ). toArray (); } }
```

### CPP

```cpp
class Solution { public: vector < int > smallestSufficientTeam ( vector < string >& req_skills , vector < vector < string >>& people ) { unordered_map < string , int > d ; int m = req_skills . size (), n = people . size (); for ( int i = 0 ; i < m ; ++ i ) { d [ req_skills [ i ]] = i ; } int p [ n ]; memset ( p , 0 , sizeof ( p )); for ( int i = 0 ; i < n ; ++ i ) { for ( auto & s : people [ i ]) { p [ i ] |= 1 << d [ s ]; } } int f [ 1 << m ]; int g [ 1 << m ]; int h [ 1 << m ]; memset ( f , 63 , sizeof ( f )); f [ 0 ] = 0 ; for ( int i = 0 ; i < 1 << m ; ++ i ) { if ( f [ i ] == 0x3f3f3f3f ) { continue ; } for ( int j = 0 ; j < n ; ++ j ) { 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 ; } } } vector < int > ans ; for ( int i = ( 1 << m ) - 1 ; i ; i = h [ i ]) { ans . push_back ( g [ i ]); } return ans ; } };
```

### Python

```python
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
```