Code Implementation

from typing import List
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill_index = {skill: i for i, skill in enumerate(req_skills)}
        n = len(req_skills)
        dp = {0: []}  # key: skill set bitmask, value: list of people indices

        for i, person in enumerate(people):
            person_skill = 0
            for skill in person:
                if skill in skill_index:
                    person_skill |= 1 << skill_index[skill]
            if person_skill == 0:
                continue
            new_dp = dp.copy()
            for skill_set, team in dp.items():
                combined = skill_set | person_skill
                if combined not in new_dp or len(new_dp[combined]) > len(team) + 1:
                    new_dp[combined] = team + [i]
            dp = new_dp
        return dp[(1 << n) - 1]
      

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int n = req_skills.size();
        unordered_map<string, int> skill_index;
        for (int i = 0; i < n; ++i) skill_index[req_skills[i]] = i;
        unordered_map<int, vector<int>> dp;
        dp[0] = {};
        for (int i = 0; i < people.size(); ++i) {
            int person_skill = 0;
            for (auto& skill : people[i]) {
                if (skill_index.count(skill)) person_skill |= 1 << skill_index[skill];
            }
            if (person_skill == 0) continue;
            auto dp_copy = dp;
            for (auto& [skill_set, team] : dp) {
                int combined = skill_set | person_skill;
                if (!dp_copy.count(combined) || dp_copy[combined].size() > team.size() + 1) {
                    dp_copy[combined] = team;
                    dp_copy[combined].push_back(i);
                }
            }
            dp = move(dp_copy);
        }
        return dp[(1 << n) - 1];
    }
};
      

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        Map<String, Integer> skillIndex = new HashMap<>();
        for (int i = 0; i < n; ++i) skillIndex.put(req_skills[i], i);
        Map<Integer, List<Integer>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        for (int i = 0; i < people.size(); ++i) {
            int personSkill = 0;
            for (String skill : people.get(i)) {
                if (skillIndex.containsKey(skill))
                    personSkill |= 1 << skillIndex.get(skill);
            }
            if (personSkill == 0) continue;
            Map<Integer, List<Integer>> newDp = new HashMap<>(dp);
            for (int skillSet : dp.keySet()) {
                int combined = skillSet | personSkill;
                List<Integer> team = new ArrayList<>(dp.get(skillSet));
                team.add(i);
                if (!newDp.containsKey(combined) || newDp.get(combined).size() > team.size()) {
                    newDp.put(combined, team);
                }
            }
            dp = newDp;
        }
        List<Integer> result = dp.get((1 << n) - 1);
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}
      

var smallestSufficientTeam = function(req_skills, people) {
    const n = req_skills.length;
    const skillIndex = new Map();
    for (let i = 0; i < n; ++i) skillIndex.set(req_skills[i], i);
    let dp = new Map();
    dp.set(0, []);
    for (let i = 0; i < people.length; ++i) {
        let personSkill = 0;
        for (const skill of people[i]) {
            if (skillIndex.has(skill))
                personSkill |= 1 << skillIndex.get(skill);
        }
        if (personSkill === 0) continue;
        const dpCopy = new Map(dp);
        for (const [skillSet, team] of dp) {
            const combined = skillSet | personSkill;
            if (!dpCopy.has(combined) || dpCopy.get(combined).length > team.length + 1) {
                dpCopy.set(combined, [...team, i]);
            }
        }
        dp = dpCopy;
    }
    return dp.get((1 << n) - 1);
};
      

Problem Description

You are given a list of required skills, req_skills, and a list of people, where each person is described by a list of the skills they have. The goal is to form the smallest sufficient team: a subset of people such that every required skill is covered by at least one person in the team, and no skill is left uncovered.

• Each person can only be used once in the team.
• There is guaranteed to be at least one valid solution.
• You must return any one such minimal team as a list of indices (not names or skills).
• Do not reuse people: each index can appear at most once in your answer.

For example, if req_skills = ["java", "nodejs", "reactjs"] and people = [["java"], ["nodejs"], ["nodejs", "reactjs"]], the answer could be [0,2] (people 0 and 2 together cover all required skills).

Thought Process

The problem is a classic example of the Set Cover problem, known to be NP-Hard. The brute-force way would be to try every possible subset of people, check if their combined skills cover all required skills, and pick the smallest such subset. However, this is not feasible when the number of people or skills grows, since there are 2ⁿ possible subsets (where n is the number of people).

To optimize, we can notice that the number of required skills is usually small (up to 16 in Leetcode), so we can use bitmasking to represent skill sets efficiently. This allows us to use dynamic programming (DP) to build up solutions for smaller skill sets and combine them to solve for larger ones.

Think of each skill set as a "state" (represented by a bitmask), and for each state, we keep track of the smallest team that can achieve it. We iteratively add people and update our DP if including them leads to a smaller team for any skill set.

Solution Approach

• Skill Indexing: Assign each required skill a unique index (0 to n-1). This lets us represent any combination of skills as an integer bitmask, where bit i is 1 if the skill at index i is covered.
• Bitmask Representation: For each person, compute a bitmask representing the skills they have. For example, if there are 3 skills and a person has the first and third, their mask is 101 (binary for 5).
• Dynamic Programming Map: Use a map (dictionary) dp where keys are skill bitmasks and values are the smallest team (list of people indices) that can achieve that skill set.
• Iterative DP Update: Start with dp[0] = [] (no skills, empty team). For each person, and for each current skill set in dp, consider adding the person. If the new combined skill set is not in dp or can be achieved with a smaller team, update dp for that skill set.
• Final Answer: The answer is dp[target], where target is the bitmask with all bits set (all skills covered).

This approach is efficient because it only depends on the number of possible skill sets (2ⁿ for n skills), not directly on the number of people.

Example Walkthrough

Let's use req_skills = ["java", "nodejs", "reactjs"] and people = [["java"], ["nodejs"], ["nodejs", "reactjs"]].

1. Assign indices: java:0, nodejs:1, reactjs:2.
2. Convert people to bitmasks:
   • Person 0: ["java"] → 001 (1)
   • Person 1: ["nodejs"] → 010 (2)
   • Person 2: ["nodejs", "reactjs"] → 110 (6)
3. Initialize dp = {0: []}.
4. Add person 0:
   • 0 | 1 = 1 → dp[1] = [0]
5. Add person 1:
   • 0 | 2 = 2 → dp[2] = [1]
   • 1 | 2 = 3 → dp[3] = [0,1]
6. Add person 2:
   • 0 | 6 = 6 → dp[6] = [2]
   • 1 | 6 = 7 → dp[7] = [0,2]
   • 2 | 6 = 6 (already exists, not smaller)
   • 3 | 6 = 7 (already exists, not smaller)
7. The target is 111 (7 in decimal). dp[7] = [0,2] is the smallest sufficient team.

Time and Space Complexity

• Brute-force: Checks all subsets of people, so time complexity is O(2ⁿ * m), where n is the number of people and m is the number of skills. This is infeasible for large n.
• Optimized DP: The number of possible skill sets is 2^m (where m is the number of skills, often ≤ 16). For each person, we may update each skill set, so time complexity is O(p * 2^m), where p is the number of people. Space complexity is also O(2^m) for the DP map.
• Why is this efficient? Because m is small, 2^m is manageable (e.g., 2¹⁶ = 65536), and p can be up to 60 or more.

Summary

The Smallest Sufficient Team problem is a practical application of the set cover problem, made tractable by using bitmasking and dynamic programming. By representing skill sets as integers and iteratively building up the minimal team for each possible combination, we avoid brute-force enumeration of all people subsets. This elegant approach leverages the small number of skills and ensures an efficient and scalable solution.