<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]:
        # smallest
        # top-down dp 
        # skill_id dict - key: skill, val:idx
        # skill set for a person with a bit masking: 101 => java, nodejs, python
        # O(2^m *n) m: skill mask, n: dp[skillsmask] O(2^m)

        n = len(people)
        m = len(req_skills)
        skill_id = {}
        all_skills = (1 << m) - 1

        for i, skill in enumerate(req_skills):# unique num for each skill
            skill_id[skill] = i

        person_skills = [0] * n # bit-mask all the skills of people
        for i in range(n):
            for skill in people[i]:
                person_skills[i] |= 1 << skill_id[skill]
        #print(person_skills) # [1,2,6]
        @cache 
        def dp(i, cur_skills): #person id, cur_skill set to be 111 required skill set
            if cur_skills == all_skills:
                return []
  
            if i == n: #not all skill collected      
                return [0] * 17 # making the longer length
            
            noPick = dp(i+1, cur_skills)
            pick = [i] + dp(i+1, cur_skills | person_skills[i]) # updating the cur_skills 0 => 1 ("java")

            return noPick if len(noPick) <= len(pick) else pick #choosing smaller one

        return dp(0,0)       



        """
        @cache #dp[skills_mask]
        def dp(skills_mask):
            res = 0
            for i in range(n):
                new_skills_mask = skills_mask & ~person_skills[i] #removing
                #print(bin(skills_mask)[2:], bin(person_skills[i])[2:], bin(~person_skills[i]), bin(new_skills_mask)[2:])
                if new_skills_mask != skills_mask:
                    people_mask = dp(new_skills_mask) | (1 << i)
                    if (res == 0 or people_mask.bit_count() < res.bit_count()):
                        res = people_mask
            return res


        res_mask = dp((1 << m) - 1) #3 skills => 1000-1 = 111: all skills
        print(res_mask) #101
        res = []
        for i in range(n):
            if (res_mask >> i) & 1: #101 => 0 and 2
                res.append(i)
        return res        
        """
58732