1125. Smallest Sufficient Team

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]

This is a classic Shortest Path problem on a graph, but because we are dealing with a small number of required skills (up to 16), we can view it as a Dynamic Programming problem with Bitmasking.

The Logic

We represent the "set of skills" as a binary number (a bitmask).

• If the required skills are ["java", "python", "react"], the mask 111 (7 in decimal) represents having all three.

• The mask 010 (2 in decimal) represents having only "python".

We want to find the smallest number of people whose combined bitmasks equal the target mask (all skills).

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        # Map skill name to its bit position
        skill_to_idx = {skill: i for i, skill in enumerate(req_skills)}
        target_mask = (1 << n) - 1
        
        # dp[mask] = list of indices of people who cover those skills
        # Initialize with the empty set for mask 0
        dp = {0: []}
        
        for i, person_skills in enumerate(people):
            # Convert current person's skills into a bitmask
            current_person_mask = 0
            for skill in person_skills:
                if skill in skill_to_idx:
                    current_person_mask |= (1 << skill_to_idx[skill])
            
            # Try to combine this person with all skill sets we've found so far
            # We iterate over a copy of keys to avoid "dictionary changed size during iteration"
            for mask, team in list(dp.items()):
                new_mask = mask | current_person_mask
                
                # If we found a new skill combination OR a shorter way to get an existing one
                if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:
                    dp[new_mask] = team + [i]
                    
        return dp[target_mask]