Smallest sufficient team

Array Dynamic Programming Bit Manipulation Bitmask

55.4% acceptance

Feb 25, 2026

2268

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn smallest_sufficient_team(req_skills: Vec<String>, people: Vec<Vec<String>>) -> Vec<i32> {
    let m = req_skills.len();
    let skill_idx: HashMap<&str, usize> = req_skills.iter().enumerate()
      .map(|(i, s)| (s.as_str(), i))
      .collect();
    let people_masks: Vec<usize> = people.iter().map(|ps| {
      ps.iter().fold(0, |acc, s| acc | (1 << skill_idx[s.as_str()]))
    }).collect();

    let full = (1usize << m) - 1;
    // dp[mask] = min team size, prev[mask] = (prev_mask, person_id)
    let mut dp = vec![usize::MAX; full + 1];
    let mut prev: Vec<(usize, i32)> = vec![(0, -1); full + 1];
    dp[0] = 0;

    for (pid, &pmask) in people_masks.iter().enumerate() {
      for curr in (0..=full).rev() {
        if dp[curr] == usize::MAX { continue; }
        let next = curr | pmask;
        if dp[next] > dp[curr] + 1 {
          dp[next] = dp[curr] + 1;
          prev[next] = (curr, pid as i32);
        }
      }
    }

    // Reconstruct
    let mut result = Vec::new();
    let mut mask = full;
    while mask != 0 {
      let (prev_mask, pid) = prev[mask];
      result.push(pid);
      mask = prev_mask;
    }
    result
  }
}