Smallest Sufficient Team

hard bitmask dynamic programming

Problem

You are given a list of required skills and a list of people, where each person knows some subset of the skills. Return the indices of any smallest team of people such that, taken together, they cover every required skill. A team is sufficient if the union of its members' skills equals the full set of required skills.

Inputskills = [java, nodejs, reactjs], people = [[java], [nodejs], [nodejs, reactjs]]

Output[0, 2]

Person 0 covers java; person 2 covers nodejs and reactjs. Together that is all three skills with only 2 people.

required skills (comma-separated)

people (one per line, skills comma-separated)

def smallestSufficientTeam(req_skills, people):
    idx = {s: i for i, s in enumerate(req_skills)}
    full = (1 << len(req_skills)) - 1
    masks = [sum(1 << idx[s] for s in p) for p in people]
    dp = {0: []}
    for i, pm in enumerate(masks):
        for have, team in list(dp.items()):
            nxt = have | pm
            if nxt == have:
                continue
            if nxt not in dp or len(dp[nxt]) > len(team) + 1:
                dp[nxt] = team + [i]
    return dp[full]

function smallestSufficientTeam(reqSkills, people) {
  const idx = {};
  reqSkills.forEach((s, i) => { idx[s] = i; });
  const full = (1 << reqSkills.length) - 1;
  const masks = people.map(p => p.reduce((m, s) => m | (1 << idx[s]), 0));
  const dp = new Map([[0, []]]);
  for (let i = 0; i < masks.length; i++) {
    for (const [have, team] of [...dp]) {
      const nxt = have | masks[i];
      if (nxt === have) continue;
      if (!dp.has(nxt) || dp.get(nxt).length > team.length + 1) {
        dp.set(nxt, team.concat(i));
      }
    }
  }
  return dp.get(full);
}

class Solution {
    public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
        int n = reqSkills.length, full = (1 << n) - 1;
        Map<String, Integer> idx = new HashMap<>();
        for (int i = 0; i < n; i++) idx.put(reqSkills[i], i);
        Map<Integer, List<Integer>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        for (int i = 0; i < people.size(); i++) {
            int pm = 0;
            for (String s : people.get(i)) pm |= 1 << idx.get(s);
            for (Map.Entry<Integer, List<Integer>> e : new HashMap<>(dp).entrySet()) {
                int nxt = e.getKey() | pm;
                if (nxt == e.getKey()) continue;
                if (!dp.containsKey(nxt) || dp.get(nxt).size() > e.getValue().size() + 1) {
                    List<Integer> team = new ArrayList<>(e.getValue());
                    team.add(i);
                    dp.put(nxt, team);
                }
            }
        }
        return dp.get(full).stream().mapToInt(Integer::intValue).toArray();
    }
}

vector<int> smallestSufficientTeam(vector<string>& reqSkills, vector<vector<string>>& people) {
    int n = reqSkills.size(), full = (1 << n) - 1;
    unordered_map<string, int> idx;
    for (int i = 0; i < n; i++) idx[reqSkills[i]] = i;
    unordered_map<int, vector<int>> dp;
    dp[0] = {};
    for (int i = 0; i < (int)people.size(); i++) {
        int pm = 0;
        for (auto& s : people[i]) pm |= 1 << idx[s];
        auto snap = dp;
        for (auto& e : snap) {
            int nxt = e.first | pm;
            if (nxt == e.first) continue;
            if (!dp.count(nxt) || (int)dp[nxt].size() > (int)e.second.size() + 1) {
                auto team = e.second;
                team.push_back(i);
                dp[nxt] = team;
            }
        }
    }
    return dp[full];
}

Explanation

We need the fewest people whose combined skills cover every required skill. Since there are only a handful of skills, we can represent any set of covered skills as a bitmask — one bit per skill — and track the smallest team that reaches each mask.

Each person becomes a mask too: bit i is set if they know skill i. The dictionary dp maps a covered-skills mask to the best (smallest) team that achieves it, starting with {0: []} meaning "no skills covered needs no one."

For each person we look at every mask already reachable and try adding them: the new mask is have | personMask. If that union is genuinely better (a new mask, or a shorter team than what we stored), we record team + [person]. This is a classic subset-cover DP over bitmasks.

Example: skills [java, nodejs, reactjs] map to bits 0,1,2 so full = 111. Person 0 (java) reaches mask 001, person 2 (nodejs, reactjs) reaches 110; combining them reaches 111 with team [0, 2] — only two people.

At the end dp[full] holds the smallest team covering all skills. With m skills there are 2^m masks, so the work is about n · 2^m.

Time: O(n · 2^m) Space: O(2^m · m)