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.

• dp solution
• Time : O(p^2)
• Space : O(2^skill)

c++

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        unordered_map<string, int> skills;
        unordered_map<int, vector<int>> dp;
        int skillId = 0;
        for(auto req : req_skills) {
            skills[req] = skillId++;
        }
        dp.reserve(1<<skillId);
        
        for(int i = 0; i < people.size(); i++) {
            int m = 0;
            for(auto skill : people[i]) {
                if(skills.count(skill)) {
                    m |= (1<<skills[skill]);
                }
            }
            if(m == 0) continue;
            dp[m] = {i};
            for(auto [mask, p] : dp) {
                int comb = mask | m;
                
                if(!dp.count(comb) or dp[comb].size() > p.size() + 1) {
                    dp[comb] = p;
                    dp[comb].push_back(i);
                }
            }
        }
        return dp[(1<<skillId) - 1];
    }
};

• backTracking solution
• Time : O(2^p)
• Space : O(1)

c++

class Solution {
    vector<int> res;
    void backTracking(vector<int>& masks, int req, vector<int>& tmp, int i) {
        if(req == 0) {
            if(res.empty() or tmp.size() < res.size()) {
                res = tmp;
            }
            return;
        }
        if(i == masks.size() or (!res.empty() and tmp.size() >= res.size())) return;
        
        if(masks[i] & req) {
            int nreq = req ^ (masks[i]&req);
            tmp.push_back(i);
            backTracking(masks, nreq, tmp, i + 1);
            tmp.pop_back();
        }
        backTracking(masks, req, tmp, i + 1);
    }
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        unordered_map<string, int> skills;
        int skillId = 0;
        for(auto req : req_skills) {
            skills[req] = skillId++;
        }
        vector<int> masks;
        for(auto peopleSkills : people) {
            int mask = 0;
            for(auto skill : peopleSkills) {
                if(skills.count(skill)) {
                    mask |= (1<<skills[skill]);
                }
            }
            masks.push_back(mask);
        }
        
        int req = (1<<skillId) - 1;
        vector<int> tmp;
        backTracking(masks, req, tmp, 0);
        return res;
    }
};