<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]:
        def findBestCandidates(req_skill_map,path):
            max_skills_covered = 0
            best_candidate_index = -1
            temp={}


            for i, person_skills in enumerate(people):
                if len(person_skills)==0:
                    continue
                if i in path:
                    continue
                skills_covered = 0
                for skill in person_skills:
                    # Check if the skill is in the map and its value is greater than 0
                    if skill in req_skill_map and req_skill_map[skill] > 0:
                        skills_covered += 1

                if skills_covered >= max_skills_covered:
                    max_skills_covered = skills_covered
                    if max_skills_covered not in temp:
                        temp[max_skills_covered]=set()
                    temp[max_skills_covered].add(i)
            #print(max_skills_covered,best_candidate_index,temp)
            keys=list(temp.keys())
            keys.sort(reverse=True)
            t=[]
            for key in keys[:2]:
                t.extend(list(temp[key]))
            t=list(set(t))
            t.sort()
            return t
        
        def reduceMap(singlePeople,skillMap):
            for skill in singlePeople:
                if skill in skillMap:
                    skillMap[skill]-=1
            return skillMap
        
        def incrementMap(singlePeople,skillMap):
            for skill in singlePeople:
                if skill in skillMap:
                    skillMap[skill]+=1
            return skillMap

        skill_map={}
        for skill in req_skills:
            if skill not in skill_map:
                skill_map[skill]=1
            else:
                skill_map[skill]+=1
        
        def validateMap(skillMap):
            for skill in skillMap:
                if skillMap[skill]>0:
                    return False
            return True

        output=[]
        minVal=float('inf')
        visited=set()
        def bt(skill_map,path):
            nonlocal minVal
            # print(skill_map,path)
            if len(path)>0 and len(path)>=minVal:
                return 
            tPath=path.copy()
            tPath.sort()
            tPath=tuple(tPath)
            if tPath in visited:
                return 
            visited.add(tPath)
            if validateMap(skill_map):
                t=path.copy()
                output.append(t)
                #print('output',output)
                minVal=len(path)
                return 
            bestIndexes=findBestCandidates(skill_map,path)
            #print('bestIndexes',bestIndexes)
            for bestIndex in bestIndexes:
                #print('bestIndex',bestIndex)
                path.append(bestIndex)
                skill_map=reduceMap(people[bestIndex],skill_map)
                #print('skill_map',skill_map)
                bt(skill_map,path)
                path.pop()
                skill_map=incrementMap(people[bestIndex],skill_map)
        t=[]
        bt(skill_map,t)
        output.sort(key=len)
        print('output')
        return output[0]

            


        

        
        
88867