[1125. Smallest Sufficient Team](https://leetcode.com/problems/smallest-sufficient-team/)

### 題目描述

In a project, you have a list of required skills `req_skills`, and a list of people. The i^th^ person `people[i]` contains a list of skills that the person has.

Consider a sufficient team: a set of people such that for every required skill in `req_skills`, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.

* For example, `team = [0, 1, 3]` represents the people with skills `people[0]`, `people[1]`, and `people[3]`.

Return *any sufficient team of the smallest possible size, represented by the index of each person*. You may return the answer in **any order**.

It is **guaranteed** an answer exists.

### 範例

**Example 1:**

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

**Example 2:**

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

**Constraints**:

* 1 <= `req_skills.length` <= 16
* 1 <= `req_skills[i].length` <= 16
* `req_skills[i]` consists of lowercase English letters.
* All the strings of `req_skills` are **unique**.
* 1 <= `people.length` <= 60
* 0 <= `people[i].length` <= 16
* 1 <= `people[i][j].length` <= 16
* `people[i][j]` consists of lowercase English letters.
* All the strings of `people[i]` are **unique**.
* Every skill in `people[i]` is a skill in `req_skills`.
* It is guaranteed a sufficient team exists.

### 解答
#### Python

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(people)
        d = {}
        i = 1
        for skill in req_skills:
            d[skill] = i
            i <<= 1
        pattern = i - 1
        people = list(map(lambda skills: sum(d[skill] for skill in skills), people))

        @cache
        def dfs(i, mask):
            if mask == 0:
                return []
            if i == n:
                return [0] * (n + 1)
            if not(mask & people[i]):
                return dfs(i + 1, mask)
            return min(dfs(i + 1, mask), [i] + dfs(i + 1, mask & ~people[i]), key=len)

        return dfs(0, pattern)

> [name=Yen-Chi Chen][time=Mon, Jul 17, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)