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.

&nbsp;
Example 1:
Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]
Example 2:
Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

&nbsp;
Constraints:


	1 &lt;= req_skills.length &lt;= 16
	1 &lt;= req_skills[i].length &lt;= 16
	req_skills[i] consists of lowercase English letters.
	All the strings of req_skills are unique.
	1 &lt;= people.length &lt;= 60
	0 &lt;= people[i].length &lt;= 16
	1 &lt;= people[i][j].length &lt;= 16
	people[i][j] consists of lowercase English letters.
	All the strings of people[i] are unique.
	Every skill in people[i] is a skill in req_skills.
	It is guaranteed a sufficient team exists.


from collections import defaultdict
from functools import lru_cache

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        N = len(req_skills)
        skills = {skill: i for i, skill in enumerate(req_skills)}
        people_mask = defaultdict(int)
        for i, cur_skills in enumerate(people):
            mask = 0
            for skill in cur_skills:
                mask |= 1<<skills[skill]
            people_mask[i] = mask
        self.path = []
        self.res = float('inf')
        self.respath = None
        @lru_cache(None)
        #i: people i
        #l: length of current self.path
        #mask: mask for current skills
        def dfs(i, l, mask):
            if mask == (1<<N) - 1:
                if l < self.res:
                    self.res = l
                    self.respath = self.path[:]
                return
            if i == len(people): return
            if l >= self.res:
                return
            dfs(i+1, l, mask)
            self.path.append(i)
            if mask & people_mask[i] != people_mask[i]: dfs(i+1, l+1, mask | people_mask[i])
            self.path.pop()
        dfs(0,0,0)
        return self.respath
class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int N = 1 << req_skills.length, INF = (int)1e9;
        int[] parent = new int[N];
        int[] who = new int[N];
        int[] dp = new int[N];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 0; i < N; i++){
            if (dp[i]!=INF){ // valid state 
                for (int k = 0; k < people.size(); k++){
                    int cur = i;
                    for (int j = 0; j < req_skills.length; j++){
                        for (String skill : people.get(k)){
                            if (req_skills[j].equals(skill)){
                                cur |= 1<<j; // set the mask
                                break;
                            }
                        }
                    }
                    if (dp[cur]>dp[i]+1){ // replace if better
                        dp[cur]=dp[i]+1;
                        parent[cur]=i;
                        who[cur]=k;
                    }
                }
            }
        }
        int[] ans = new int[dp[N-1]];
        for (int i = 0,cur=N-1; i < ans.length; i++){
            ans[i]=who[cur];
            cur=parent[cur];
        }
        return ans;
    }
}
class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        vector<int> mask(people.size(), 0);
        for(int i=0; i<people.size(); i++){
            for(int j=0; j<req_skills.size(); j++){
                for(int z=0; z<people[i].size(); z++){
                    if(people[i][z] == req_skills[j]){
                        mask[i] += (1<<j);
                        break;
                    }
                }
            }
        }
        vector<long long> dp(1<<req_skills.size(), INT_MAX);
        vector<vector<int>> save(1<<req_skills.size());
        dp[0] = 0;
        for(int i=0; i<(1<<req_skills.size()); i++){
            for(int j=0; j<mask.size(); j++){
                int new_mask = i&(i^mask[j]);
                if(dp[new_mask]+1<dp[i]){
                    dp[i] = dp[new_mask]+1;
                    save[i] = save[new_mask];
                    save[i].push_back(j);
                }
            }
        }
        return save[(1<<req_skills.size())-1];
        
    }
};
/**
 * @param {string[]} req_skills
 * @param {string[][]} people
 * @return {number[]}
 */
var smallestSufficientTeam = function(req_skills, people) {
    
    const skillIndexMap = new Map();
    
    req_skills.forEach((skill, index) => skillIndexMap.set(skill,index) );
    
    const skillTeamMap = new Map([[0, []]]);
    
    people.forEach( (skills, index) => {
        
        let hisSkills = 0;
                
        for (const skill of skills) {
            hisSkills |= 1 << skillIndexMap.get(skill);
        }
                
        for (const [currSkill, team] of skillTeamMap) {
            
            const totalSkills = currSkill | hisSkills;
            
            if (totalSkills === currSkill) {
                continue;
            }
            
            if (    
                !skillTeamMap.has(totalSkills) || 
                team.length + 1 < skillTeamMap.get(totalSkills).length
            ) {                
                skillTeamMap.set(totalSkills, [...team, index])
            }             
        }
    });
        
    return skillTeamMap.get( (1<<req_skills.length) - 1);
};
Smallest Sufficient Team