1
# Runtime: 2036 ms (Top 22.82%) | Memory: 203 MB (Top 6.04%)
2
from collections import defaultdict
3
from functools import lru_cache
4

5

6
class Solution:
7
    def smallestSufficientTeam(
8
        self, req_skills: List[str], people: List[List[str]]
9
    ) -> List[int]:
10
        N = len(req_skills)
11
        skills = {skill: i for i, skill in enumerate(req_skills)}
12
        people_mask = defaultdict(int)
13
        for i, cur_skills in enumerate(people):
14
            mask = 0
15
            for skill in cur_skills:
16
                mask |= 1 << skills[skill]
17
            people_mask[i] = mask
18
        self.path = []
19
        self.res = float("inf")
20
        self.respath = None
21

22
        @lru_cache(None)
23
        # i: people i
24
        # l: length of current self.path
25
        # mask: mask for current skills
26
        def dfs(i, l, mask):
27
            if mask == (1 << N) - 1:
28
                if l < self.res:
29
                    self.res = l
30
                    self.respath = self.path[:]
31
                return
32
            if i == len(people):
33
                return
34
            if l >= self.res:
35
                return
36
            dfs(i + 1, l, mask)
37
            self.path.append(i)
38
            if mask & people_mask[i] != people_mask[i]:
39
                dfs(i + 1, l + 1, mask | people_mask[i])
40
            self.path.pop()
41

42
        dfs(0, 0, 0)
43
        return self.respath