<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]:
        #initialize a map of skills to power of 2 for binary representation 
        skills_to_index = {skill: 1<<i for i, skill in enumerate(req_skills)}

        #total skills required represented as a binary number 
        total_skills_needed = 2**len(req_skills)-1

        #Placeholder for a large number of our DP case. We cant return inf 
        #and we can't and or or with inf
        MAX_NUM = 2**(len(people)+1) - 1 

        #Rep each person's skills and their own unique index as a binary number 
        person_skills_mask = [0]*len(people)
        unique_index = [1<<i for i in range(len(people))]
        for i, person in enumerate(people):
            for skill in person: 
                person_skills_mask[i] |= skills_to_index[skill]

        #store intermediate results to avoid recomputation 
        visited = defaultdict(int)
        #recursive fn for dynamic programming 
        def dp(person_index, skills_needed):
            #if no more skills are needed, we dont' need any more people 
            if skills_needed == 0: 
                return 0 
            #if we considered all people and still need skills, return a large num
            if person_index == len(people):
                return MAX_NUM 
            #if this scenario has been considered before, return the result 
            if (person_index, skills_needed) in visited: 
                return visited[(person_index, skills_needed)]
            #initialize result to scenario where curr person isn't included in team
            res = dp(person_index + 1, skills_needed)
            #skills needed after considering curr person's skills
            remaining_skills = skills_needed & (~person_skills_mask[person_index])
            #if the cur persn has some of the skills needed, consider scenario
            #where they are included in the team
            if remaining_skills < skills_needed:
                team_with_person = unique_index[person_index] | dp(person_index + 1, remaining_skills)
                #if including cur prsn rslts in a smlr team, update the reslt 
                if bin(team_with_person).count('1') < bin(res).count('1'):
                    res = team_with_person
            visited[(person_index, skills_needed)] = res 
            return res 

        res = dp(0, total_skills_needed)
        min_team_indices = [i for i in range(len(people)) if res & (1<<i)]#conversion back to indices.

        return min_team_indices
        #TC: time(p*2^s)
        #SC: p*2^s

        #https://www.youtube.com/watch?v=Ev92oky6aLM
        #line 40 is equivalent to res= 1 +dp(next_index+1)
        #as we're dealing with bit masks, we do this. In this case, 
        #we're considering the person and his skills.
        
68777