Similar Problems

Similar Problems not available

Smallest Sufficient Team - Leetcode Solution


  • google

LeetCode:  Smallest Sufficient Team Leetcode Solution

Difficulty: Hard

Topics: dynamic-programming bit-manipulation array  

The Smallest Sufficient Team problem on LeetCode is to given a list of requirements and a list of team members' skills, find the smallest possible team that can cover all the requirements. The problem can be solved using dynamic programming.


Step 1: Convert the requirements and team members' skills to binary strings. Each requirement and skill corresponds to a bit in the binary string. If the skill or requirement is present, the bit is set to 1, otherwise it is set to 0.

Step 2: Create a dictionary to store the minimum number of team members required to cover each state of the requirements. The state is represented by a binary string.

Step 3: The base case is when all the requirements are covered, the minimum number of team members required is 0. Add this to the dictionary.

Step 4: For each team member, generate all the states that can be covered by this team member. For each state, check if the current number of team members required to cover this state is less than the previously computed value. If yes, update the dictionary with the new minimum value.

Step 5: The final answer is the value in the dictionary for the state that covers all the requirements.


Here is the Python code to solve the Smallest Sufficient Team problem on LeetCode.

def smallestSufficientTeam(req_skills, people): n = len(req_skills) m = len(people) skill_dict = {} for i in range(n): skill_dict[req_skills[i]] = i people_skills = [] for i in range(m): skill_set = set() for skill in people[i]: skill_set.add(skill_dict[skill]) people_skills.append(skill_set) # Dictionary to store minimum number of team members required for each state dp = {} # Base case dp[(1 << n) - 1] = 0 for i in range(m): # Generate all states that can be covered by this team member state = 0 for j in people_skills[i]: state |= (1 << j) for key in list(dp): if key & state == state: new_key = key ^ state if new_key not in dp or dp[new_key] > dp[key] + 1: dp[new_key] = dp[key] + 1 # Final answer return dp[0]


req_skills = ["java", "nodejs", "reactjs"] people = [["java"], ["nodejs"], ["nodejs", "reactjs"]] print(smallestSufficientTeam(req_skills, people)) # Output: 2

Smallest Sufficient Team Solution Code