Smallest Sufficient Team

• The core idea is to explore all possible subsets of people.
• A recursive function, say backtrack(index, current_team, current_mask), is used.
• index is the index of the person to consider.
• current_team is the list of people indices chosen so far.
• current_mask is a bitmask of the skills covered by the current_team.
• Base Case: When index reaches the end of the people list, if current_mask covers all required skills, we compare current_team's size with the best solution found so far and update if it's smaller.
• Recursive Step: For the person at index, we make two recursive calls:
  1. Exclude: backtrack(index + 1, current_team, current_mask).
  2. Include: Add the person to current_team, update current_mask, and call backtrack(index + 1, ...).
• Pruning: An important optimization is to stop exploring a branch if the current_team size is already greater than or equal to the smallest team found so far.

The backtracking algorithm systematically generates all combinations of people. It uses a recursive function that, for each person, decides whether to include them in the team or not. This creates a search tree where each path from the root to a leaf represents a potential team.

We maintain a bitmask to keep track of the skills covered by the team being built. A bitmask is an integer where the i-th bit is set if the i-th required skill is covered. The target is a mask where all bits corresponding to required skills are set.

To make this feasible for very small inputs, we must use pruning. If at any point the size of the team we are currently building becomes equal to or larger than the size of the best solution we've already found, we can abandon that path of exploration (prune the search tree). However, since the number of people can be up to 60, the number of subsets is 2^60, which is far too large to explore even with pruning.

1class Solution {2    List<Integer> smallestTeam = new ArrayList<>();3    int[] pSkills;4    int n, m;5    int targetMask;6 7    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {8        n = req_skills.length;9        m = people.size();10        targetMask = (1 << n) - 1;11        12        Map<String, Integer> skillMap = new HashMap<>();13        for (int i = 0; i < n; i++) {14            skillMap.put(req_skills[i], i);15        }16 17        pSkills = new int[m];18        for (int i = 0; i < m; i++) {19            for (String skill : people.get(i)) {20                pSkills[i] |= (1 << skillMap.get(skill));21            }22        }23 24        for (int i = 0; i < m; i++) smallestTeam.add(i); // Initialize with a team of all people25 26        backtrack(0, new ArrayList<>(), 0);27 28        int[] result = new int[smallestTeam.size()];29        for (int i = 0; i < smallestTeam.size(); i++) {30            result[i] = smallestTeam.get(i);31        }32        return result;33    }34 35    private void backtrack(int p_idx, List<Integer> currentTeam, int mask) {36        if (mask == targetMask) {37            if (currentTeam.size() < smallestTeam.size()) {38                smallestTeam = new ArrayList<>(currentTeam);39            }40            return;41        }42 43        if (p_idx == m || currentTeam.size() >= smallestTeam.size()) {44            return;45        }46 47        // Exclude person p_idx48        backtrack(p_idx + 1, currentTeam, mask);49 50        // Include person p_idx51        currentTeam.add(p_idx);52        backtrack(p_idx + 1, currentTeam, mask | pSkills[p_idx]);53        currentTeam.remove(currentTeam.size() - 1);54    }55}

• First, map each skill to a unique index from 0 to n-1 to enable bitmasking.
• Compute a skill bitmask for each person.
• Create a DP table, dp, of size 2^n, where dp[mask] will store the list of people forming the smallest team for the skills in mask.
• Initialize dp[0] to an empty list. All other entries are null.
• Iterate through each person p from 0 to m-1.
• For each person, iterate through all existing skill masks j from (1 << n) - 1 down to 0.
• If dp[j] is not null (meaning a team for mask j exists), calculate next_mask = j | p_skills[p].
• If no team exists for next_mask yet, or if the new team (dp[j].size() + 1) is smaller than the existing team for next_mask, update dp[next_mask] by creating a copy of dp[j] and adding person p.
• The final answer is the list stored in dp[(1 << n) - 1].

The key insight is to use the set of acquired skills as the DP state. Since there are at most 16 skills, we can represent any subset of skills with a 16-bit integer, or a bitmask. Let dp[mask] be the smallest team (represented as a list of people indices) that collectively has the skills represented by mask.

The DP table dp will have 2^n entries. We initialize dp[0] as an empty team. Then, we process each person one by one. For each person p with skills p_skills, we can potentially improve the teams for various skill masks. We iterate through all masks j for which we already have a solution dp[j]. By adding person p to the team dp[j], we get a new team that covers skills j | p_skills. If this new team is smaller than any previously found team for j | p_skills, we update dp[j | p_skills].

An important detail is to iterate the masks j in decreasing order. This ensures that when we consider person p, all updates are based on teams formed by people before p, preventing person p from being used to update a state that is then used again in the same iteration.

As a practical optimization, we can pre-process the list of people to remove any person whose skill set is a strict subset of another person's skill set. This can reduce m, the number of people, and speed up the computation, though it doesn't change the worst-case complexity.

1class Solution {2    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {3        int n = req_skills.length;4        int m = people.size();5        Map<String, Integer> skillMap = new HashMap<>();6        for (int i = 0; i < n; i++) {7            skillMap.put(req_skills[i], i);8        }9 10        List<Integer>[] dp = new List[1 << n];11        dp[0] = new ArrayList<>();12 13        for (int i = 0; i < m; i++) {14            int pSkill = 0;15            for (String skill : people.get(i)) {16                pSkill |= (1 << skillMap.get(skill));17            }18 19            for (int j = (1 << n) - 1; j >= 0; j--) {20                if (dp[j] == null) continue;21 22                int nextMask = j | pSkill;23                if (dp[nextMask] == null || dp[j].size() + 1 < dp[nextMask].size()) {24                    List<Integer> newTeam = new ArrayList<>(dp[j]);25                    newTeam.add(i);26                    dp[nextMask] = newTeam;27                }28            }29        }30 31        List<Integer> resList = dp[(1 << n) - 1];32        return resList.stream().mapToInt(i -> i).toArray();33    }34}

• Map skills to indices and compute person skill masks, just like in the previous approach.
• Create a DP array dp of size 2^n to store the size of the smallest team for each mask. Initialize dp[0] = 0 and all other entries to a value larger than m (infinity).
• Create two additional arrays, parent_mask and parent_person, both of size 2^n, to store pointers for reconstructing the solution path.
• Iterate through each person p and then through all masks j from (1 << n) - 1 down to 0.
• For each state j, calculate the next_mask = j | p_skills[p].
• If dp[j] + 1 < dp[next_mask], it means we've found a smaller team for next_mask. Update dp[next_mask] = dp[j] + 1, and store the backtracking information: parent_mask[next_mask] = j and parent_person[next_mask] = p.
• After the loops complete, dp[(1 << n) - 1] holds the size of the smallest team.
• Reconstruct the team by starting from the final mask (1 << n) - 1 and following the parent_mask and parent_person pointers back to mask 0, collecting the person indices along the way.

The core logic remains the same as the previous DP approach, but we optimize the data storage. The DP state dp[mask] now only stores an integer representing the minimum team size for covering the skills in mask.

To be able to find the actual team members, we need to record the choice that led to each optimal value. We use two helper arrays: parent_person[mask] stores the index of the last person added to form the optimal team for mask, and parent_mask[mask] stores the skill mask that the team had before this last person was added.

The DP transition is: when considering person p and a previous state j, if adding p creates a smaller team for next_mask = j | p_skills[p], we update dp[next_mask] with the new smaller size and record p and j as the parents of this new state.

Once the DP table is fully populated, we can find the members of the smallest sufficient team by starting at the target mask (1 << n) - 1. We add parent_person[(1 << n) - 1] to our result team, then move to the state parent_mask[(1 << n) - 1], and repeat this process until we trace our way back to the initial mask 0.

This avoids the expensive list copying operations within the main DP loops, significantly improving performance.

1class Solution {2    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {3        int n = req_skills.length;4        int m = people.size();5        Map<String, Integer> skillMap = new HashMap<>();6        for (int i = 0; i < n; i++) {7            skillMap.put(req_skills[i], i);8        }9 10        int[] pSkills = new int[m];11        for (int i = 0; i < m; i++) {12            for (String skill : people.get(i)) {13                pSkills[i] |= (1 << skillMap.get(skill));14            }15        }16 17        int[] dp = new int[1 << n];18        Arrays.fill(dp, m + 1);19        dp[0] = 0;20        int[] parent_mask = new int[1 << n];21        int[] parent_person = new int[1 << n];22 23        for (int i = 0; i < m; i++) {24            if (pSkills[i] == 0) continue;25            for (int j = (1 << n) - 1; j >= 0; j--) {26                if (dp[j] >= m) continue;27                int nextMask = j | pSkills[i];28                if (dp[j] + 1 < dp[nextMask]) {29                    dp[nextMask] = dp[j] + 1;30                    parent_mask[nextMask] = j;31                    parent_person[nextMask] = i;32                }33            }34        }35 36        List<Integer> res = new ArrayList<>();37        int currentMask = (1 << n) - 1;38        while (currentMask != 0) {39            res.add(parent_person[currentMask]);40            currentMask = parent_mask[currentMask];41        }42        return res.stream().mapToInt(i -> i).toArray();43    }44}