1125. Smallest Sufficient Team

link

Make the skill as state, so each workers should have different state

# {11001, 00100, 10101, 00011 .....}  1 = owned , 0 = not owned
# => find mininum step to make -> { 11111 }

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:

        rq = { value: key for key , value in enumerate(req_skills) }

        finalState = (1 << len(rq)) - 1

        pre = []

        for skills in people:
            cur = 0
            for skill in skills:
                cur += 1 << rq[skill]
            pre.append(cur)

        for i in range(len(pre)):
            for j in range(len(pre)):
                if i == j:
                    continue
                
                if pre[i] | pre[j] == pre[i]:
                    pre[j] = 0        

        @cache
        def backtrack(s, state):
            if state == finalState:
                return []
            if s == len(pre):
                return [0] * 100 # means impossible
            
            r1 = backtrack(s+1, state)
            r2 = backtrack(s+1, state  | pre[s]) + [s]

            # get array with fewer elements
            return min (backtrack(s+1, state) , backtrack(s+1, state  | pre[s]) + [s], key=len)

        res = backtrack(0, 0)

        return res