<p>In a project, you have a list of required skills <code>req_skills</code>, and a list of people. The <code>i<sup>th</sup></code> person <code>people[i]</code> contains a list of skills that the person has.</p>

<p>Consider a sufficient team: a set of people such that for every required skill in <code>req_skills</code>, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.</p>

<ul>
	<li>For example, <code>team = [0, 1, 3]</code> represents the people with skills <code>people[0]</code>, <code>people[1]</code>, and <code>people[3]</code>.</li>
</ul>

<p>Return <em>any sufficient team of the smallest possible size, represented by the index of each person</em>. You may return the answer in <strong>any order</strong>.</p>

<p>It is <strong>guaranteed</strong> an answer exists.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
<strong>Output:</strong> [0,2]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
<strong>Output:</strong> [1,2]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        pass




























class Solution:
    def smallestSufficientTeam(self, req_skills: List[str],
                               people: List[List[str]]) -> List[int]:
        n = len(people)
        m = len(req_skills)

        # skill string --> index
        skill_id = dict()
        for i, skill in enumerate(req_skills):
            skill_id[skill] = i

        # person's skills --> binary marker
        skills_mask_of_person = [0] * n
        for i in range(n):
            for skill in people[i]:
                skills_mask_of_person[i] |= 1 << skill_id[skill]
        
        # dp[skillMask] = people_mask
        #   - bitmask representing the smallest team covering skillMask
        # dp: initialize to 1111..1 (size of people), dp's size is 2**m (size of skills)
        #   - Goal is to get dp[1111...1 (size of skills)]
        dp = [(1 << n) - 1] * (1 << m)
        dp[0] = 0
        for skills_mask in range(1, 1 << m): # iterate over all possible combinations of skills
            for i in range(n): # iterate over people
                # For each skills_mask, find the minimum number of people covering it. 

                smaller_skills_mask = skills_mask & ~skills_mask_of_person[i]
                # smaller_skills_mask = current combination of skills - skills_mask_of_person 
                #   --> remaining skills that are cannot be covered by the person[i]
                # if smaller_skills_mask == skills_mask
                #   --> current person[i]'s skill does not overlap with the current skills_mask
                # if smaller_skills_mask != skills_mask
                #   --> there is an overlap. 
                if smaller_skills_mask != skills_mask:
                    people_mask = dp[smaller_skills_mask] | (1 << i)
                    # dp[smaller_skills_mask] stores min people that covers smaller_skills_mask.
                    # if smaller_skills_mask != skills_mask, 
                    #   --> it means the current people[i] has skills that overlap with skills_mask.
                    #   --> from skills_mask, by excluding people[i]'s skills, it becomes smaller_skills_mask
                    #   --> from smaller_skills_mask, bt including people[i]'s skills, it becomes skills_mask
                    # people_mask is bitmask of poeple that covers skills_mask
                    # if there are less number of people in people_mask than the current dp[skills_mask], update. 
                    if people_mask.bit_count() < dp[skills_mask].bit_count():
                        dp[skills_mask] = people_mask

        answer_mask = dp[(1 << m) - 1] # dp[11..1 (size of skills)]
        ans = []
        for i in range(n): # iterate over people
            if (answer_mask >> i) & 1:
                ans.append(i)
        return ans





















class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        '''
        req_skills: idx --> skill (str)
        skill_id: skill (str) --> idx
        people: idx --> list(str)
        skill_mask_of_person: idx --> binary mask of skills

        dp[skill_combination] = binary_mask of min people covering skill_combination
        '''
        m, n = len(req_skills), len(people)
        
        skill_id = {}
        for i in range(m):
            skill_id[req_skills[i]] = i
        
        skills_mask_of_person = [0] * n
        for i in range(n):
            for skill in people[i]:
                sid = skill_id[skill]
                skills_mask_of_person[i] |= 1 << sid

        dp = [(1<<n)-1] * (1<<m)
        dp[0] = 0
        for skills_mask in range(1, 1<<m):
            for i in range(n):
                smaller_skills_mask = skills_mask & (~skills_mask_of_person[i])
                
                if smaller_skills_mask != skills_mask:
                    # overlap exists
                    people_mask = dp[smaller_skills_mask] | (1 << i)
                    if people_mask.bit_count() < dp[skills_mask].bit_count():
                        dp[skills_mask] = people_mask

        answer_mask = dp[(1<<m)-1]
        ans = []
        for i in range(n):
            if (answer_mask >> i) & 1:
                ans.append(i)
        return ans































class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        '''
        dp[skill_set] = min_team_mask
        req_skills: idx --> skills (str)
        skill_ids: skill (str) --> idx
        people: idx --> list(skills)
        skill_mask_of_person: idx --> skill_mask
        '''
        skill_ids = {}
        for idx, skill in enumerate(req_skills):
            skill_ids[skill] = idx
        
        skill_mask_or_person = {}
        for idx in range(len(people)):
            skill_mask = 0
            for skill in people[idx]:
                skill_id = skill_ids[skill]
                skill_mask |= (1 << skill_id)
            skill_mask_or_person[idx] = skill_mask
        
        n_skills = len(req_skills)
        n_people = len(people)
        
        dp = [(1 << n_people)-1] * (1 << n_skills)
        dp[0] = 0
        print(dp)
        print(skill_mask_or_person)
        for skill_combs in range(1 << n_skills):
            for idx_people in range(n_people):
                min_skills = skill_combs & (~skill_mask_or_person[idx_people])
                # skills without the current person. 

                if min_skills != skill_combs:
                    people_mask = dp[min_skills] | (1 << idx_people)
                    # if there is an overlap between the current skill set and skills of a person
                    if people_mask.bit_count() < dp[skill_combs].bit_count():
                        dp[skill_combs] = people_mask
        
        print(dp[-1])
        print(dp)
        ans_mask = dp[-1]
        ans_team = []
        for i in range(n_people):
            if (ans_mask >> i) & 1 == 1:
                ans_team.append(i)
        return ans_team



























class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        '''
        req_skills: int --> skills (str)
        skill_ids: skills (str) --> int
        people: int --> list(str)
        skill_mask_of_person: int --> binary skill mask
        '''
        n_skills = len(req_skills)
        n_people = len(people)

        skill_ids = {}
        for i, skill in enumerate(req_skills):
            skill_ids[skill] = i
        
        skill_mask_of_person = [0] * n_people
        for i in range(len(people)):
            for skill in people[i]:
                skill_mask_of_person[i] |= (1 << skill_ids[skill])
        
        '''
        dp[skill_combination] = min_team_mask
        '''
        dp = [(1<<n_people)-1] * (1 << n_skills)
        dp[0] = 0
        
        for skill_mask in range(1<<n_skills):
            for idx_people in range(n_people):
                min_skill_mask = skill_mask & ~skill_mask_of_person[idx_people]

                if min_skill_mask != skill_mask:
                    # overlap exists for the current person's skills
                    team_mask = dp[min_skill_mask] | (1 << idx_people)
                    if team_mask.bit_count() < dp[skill_mask].bit_count():
                        dp[skill_mask] = team_mask
        
        team_mask = dp[-1]
        team = []
        for i in range(n_people):
            if (team_mask >> i) & 1:
                team.append(i)
        return team



























class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        '''
        req_skills: int --> str (skills)
        skill_ids: str (skills) --> int
        people: int --> list(skills)
        skill_maks_of_people: int --> binary mask of skills
        '''
        skill_ids = {}
        for idx, skill in enumerate(req_skills):
            skill_ids[skill] = idx
        
        skill_mask_of_people = collections.defaultdict(int)
        for idx_people in range(len(people)):
            skills = people[idx_people]
            for skill in skills:
                skill_id = skill_ids[skill]
                skill_mask_of_people[idx_people] |= (1 << skill_id)

        '''
        dp[skill_combination_mask] = min_people_combination_mask
        '''
        dp = [(1<<len(people))-1] * (1<<len(req_skills))
        dp[0] = 0
        for comb_skills in range(1<<len(req_skills)):
            for idx_people in range(len(people)):
                min_skills = comb_skills & (~skill_mask_of_people[idx_people])

                if min_skills != comb_skills:
                    # overlap exists
                    team_mask = dp[min_skills] | (1 << idx_people)
                    if team_mask.bit_count() < dp[comb_skills].bit_count():
                        dp[comb_skills] = team_mask
        
        mask_ans = dp[-1]
        team_ans = []
        for i in range(len(people)):
            if (mask_ans >> i) & 1 == 1:
                team_ans.append(i)
        return team_ans


























class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        '''
        skill_ids: skill (str) --> idx
        skill_mask_of_person: idx_people --> skill_masks
        '''
        skill_ids = {}
        for idx, skill in enumerate(req_skills):
            skill_ids[skill] = idx
        skill_mask_of_person = {}
        for idx_people in range(len(people)):
            skill_mask = 0
            for skill in people[idx_people]:
                skill_id = skill_ids[skill]
                skill_mask |= (1 << skill_id)
            skill_mask_of_person[idx_people] = skill_mask
        
        '''
        dp: skill_mask --> min_team_mask
        '''
        dp = [(1 << len(people))-1] * (1<<len(req_skills))
        dp[0] = 0
        for skill_comb in range(1<<len(req_skills)):
            for idx_people in range(len(people)):
                min_skill_mask = skill_comb & (~skill_mask_of_person[idx_people])

                if min_skill_mask != skill_comb:
                    # overlap exitst for current idx_people
                    team_mask = dp[min_skill_mask] | (1<<idx_people)
                    if team_mask.bit_count() < dp[skill_comb].bit_count():
                        dp[skill_comb] = team_mask

        ans_mask = dp[-1]
        team_mask = []
        for i in range(len(people)):
            if (ans_mask >> i) & 1 == 1:
                team_mask.append(i)
        return team_mask

























class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        '''
        req_skills: int --> skill (str)
        people: int --> list(skills)

        skill_ids: skill (str) --> int
        skill_mask_of_person: int --> binary skill mask
        '''
        skill_ids = {}
        for i, skill in enumerate(req_skills):
            skill_ids[skill] = i
        skill_mask_of_person = {}
        for i, skills in enumerate(people):
            skill_mask = 0
            for skill in skills:
                skill_mask |= (1 << skill_ids[skill])
            skill_mask_of_person[i] = skill_mask

        '''
        dp: skill_mask --> minimum team 
        dp[skill_mask] = min_team_mask
        '''
        dp = [(1<<len(people))-1] * (1<<len(req_skills))
        dp[0] = 0
        for skill_comb in range(1, 1<<len(req_skills)):
            for idx_people in range(len(people)):
                min_skill_mask = skill_comb & (~skill_mask_of_person[idx_people])

                if min_skill_mask != skill_comb:
                    # overlap exitst
                    team_mask_new = dp[min_skill_mask] | (1<<idx_people)
                    
                    if dp[skill_comb].bit_count() > team_mask_new.bit_count():
                        dp[skill_comb] = team_mask_new
        
        skill_mask_ans = dp[-1]
        team_ans = []
        for i in range(len(people)):
            if (skill_mask_ans >> i) & 1 == 1:
                team_ans.append(i)
        return team_ans























class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill_ids = {} # str --> idx
        skill_mask_of_person = {} # idx --> skill mask
        for idx, skill in enumerate(req_skills):
            skill_ids[skill] = idx

        for idx, skills in enumerate(people):
            masks = 0
            for skill in skills:
                masks |= (1 << skill_ids[skill])
            skill_mask_of_person[idx] = masks

        skill_ids = {}
        for i, skill in enumerate(req_skills):
            skill_ids[skill] = i
        skill_mask_of_person = {}
        for i, skills in enumerate(people):
            skill_mask = 0
            for skill in skills:
                skill_mask |= (1 << skill_ids[skill])
            skill_mask_of_person[i] = skill_mask
        
        # dp[skill_combination_mask] = min number of team mask
        dp = [(1<<len(people))-1] * (1<<len(req_skills))
        dp[0] = 0
        for skill_mask in range(1, 1<<len(req_skills)):
            for idx_person in range(len(people)):
                skill_mask_min = skill_mask & (~skill_mask_of_person[idx_person])
                if skill_mask_min != skill_mask:
                    # overlap exists
                    min_team_mask_new = dp[skill_mask_min] | (1<<idx_person)
                    if min_team_mask_new.bit_count() < dp[skill_mask].bit_count():
                        dp[skill_mask] = min_team_mask_new
        team_mask_ans = dp[-1]
        team_list = []
        for i in range(len(people)):
            if (team_mask_ans >> i) & 1 == 1:
                team_list.append(i)
        return team_list

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        '''
        req_skills: int --> str
        people: int --> list(str)

        skill_ids: str --> int
        skill_mask_of_person: idx --> skill_mask
        '''

        skill_ids = {}
        for idx, skill in enumerate(req_skills):
            skill_ids[skill] = idx
        skill_mask_of_person = [0] * len(people)
        for idx in range(len(people)):
            mask = 0
            for skill in people[idx]:
                mask |= (1 << skill_ids[skill])
            skill_mask_of_person[idx] = mask

        # dp: skill_combination --> min_team_mask
        # dp[skill_mask] = min_team_mask
        dp = [(1 << len(people)) - 1] * (1 << len(req_skills))
        dp[0] = 0

        for skill_mask in range(1 << len(req_skills)):
            for idx_person in range(len(people)):
                min_skill_mask = skill_mask & (~skill_mask_of_person[idx_person])

                if min_skill_mask != skill_mask:
                    min_team_mask = dp[min_skill_mask] | (1 << idx_person)
                    if min_team_mask.bit_count() < dp[skill_mask].bit_count():
                        dp[skill_mask] = min_team_mask
        
        ans_team_mask = dp[-1]
        ans_team_list = []
        for i in range(len(people)):
            if (ans_team_mask >> i) & 1 == 1:
                ans_team_list.append(i)
        return ans_team_list
19987