## Algorithm

Problem Name: 1125. Smallest Sufficient Team

In a project, you have a list of required skills `req_skills`, and a list of people. The `ith` 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.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const smallestSufficientTeam = function(req_skills, people) {
const m = req_skills.length
const n = people.length
const skill2Bitmap = req_skills
.map((x, i) => [x, i])
.reduce((dict, cur) => {
dict[cur[0]] = 1 << cur[1]
return dict
}, {})
const newPeople = people.map(x => {
return x.reduce((acc, cur) => {
const y = skill2Bitmap[cur]
if (y !== undefined) {
acc |= y
}
return acc
}, 0)
})

const all = (1 << m) - 1
const dp = {}
for (let j = 0; j  <  n; j++) {
if (newPeople[j] > 0) {
dp[newPeople[j]] = new Set([j])
}
}
if (dp[all]) {
return Array.from(dp[all]).sort()
}

for (let k = 0; k  <  n; k++) {
for (let s in dp) {
for (let j = 0; j  <  n; j++) {
if (newPeople[j] === 0 || dp[s].has(j)) continue
const newIdx = s | newPeople[j]
if (dp[newIdx] === undefined) {
dp[newIdx] = new Set([...dp[s], j])
if (newIdx === all) {
return Array.from(dp[all]).sort()
}
}
}
}
}
return []
}
``````
Copy The Code &

Input

cmd
req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]

Output

cmd
[0,2]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
n, m = len(req_skills), len(people)
key = {v: i for i, v in enumerate(req_skills)}
dp = {0: []}
for i, p in enumerate(people):
his_skill = 0
for skill in p:
if skill in key:
his_skill |= 1 << key[skill]
for skill_set, need in list(dp.items()):
with_him = skill_set | his_skill
if with_him == skill_set: continue
if with_him not in dp or len(dp[with_him]) > len(need) + 1:
dp[with_him] = need + [i]
return dp[(1 << n) - 1]
``````
Copy The Code &

Input

cmd
req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]

Output

cmd
[0,2]