Python Greedy DFS with pruning
\n\n\n\n\n\nThe idea is to DFS over all the skills. we maintain a peopleSet, in level K of DFS, we check whether we already have people in peopleSet can do req_
\n\n\n\n\n\nThe idea is to DFS over all the skills. we maintain a peopleSet, in level K of DFS, we check whether we already have people in peopleSet can do req_skills[k]. If so, we go to next level with same peopleSet; otherwise we loop over all people who can do req_skills[k], add them to the peopleSet and go to the next level.\n\n\n\tdef smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n       \n\t    skillGraph = defaultdict(set)\n        N = len(req_skills)\n        for ind, p in enumerate(people):\n            for skill in p:\n                skillGraph[skill].add(ind)\n        \n        ans = list(range(N+1))\n        \n        def DFS(peopleSet, k):\n            nonlocal ans\n            if k == N:\n                if len(ans) > len(peopleSet):\n                    ans = list(peopleSet)\n                return \n            if len(peopleSet) >= len(ans):\n                return \n            for p in peopleSet:\n                if p in skillGraph[req_skills[k]]:\n                    DFS(peopleSet, k+1)\n                    return \n            for p in skillGraph[req_skills[k]]:\n                peopleSet.add(p)\n                DFS(peopleSet, k+1)\n                peopleSet.remove(p)\n        \n        DFS(set(), 0)\n        \n        return ans
[]