Problem statement

https://leetcode.com/problems/smallest-sufficient-team/

Solution 1

dp(i, mask) is minimum number of people needed to cover mask if we already covered i persons. This function will return two values: (minimum number of people, last taken), we need it to recunstuct answer.

Complexity

Time and space complexity is O(k*2^n)

Code

class Solution:
    def smallestSufficientTeam(self, req_skills, people):
        d = {s:i for i, s in enumerate(req_skills)}
        masks = [sum(1<<d[skill] for skill in p) for p in people]
        n, k = len(req_skills), len(people)
        
        @lru_cache(None)
        def dp(i, mask):
            if i == -1: return (mask*1000, -1)
            cand1 = dp(i-1, mask)
            cand2 = (dp(i-1, mask & ~masks[i])[0] + 1, i)
            return min(cand1, cand2)

        mask, ans =  (1<<n) - 1, []
        while mask:
            steps, last = dp(k - 1, mask)
            ans.append(last)
            mask &= ~masks[last]

        return ans

Solution 2

Actually, we can write it in more shorter way if we keep not the last person used, but bitmask of used one (we have at most 60, so it will fit in long not only in python)

Complexity

It is the same as previous approach: time and space is O(k*2^n).

Code

class Solution:
    def smallestSufficientTeam(self, req_skills, people):
        d = {s:i for i, s in enumerate(req_skills)}
        masks = [sum(1<<d[s] for s in p) for p in people]
        n, k = len(req_skills), len(people)
        
        @lru_cache(None)
        def dp(i, mask):
            if i == -1: return (mask*1000, 0)
            steps, peop = dp(i-1, mask & ~masks[i])
            return min(dp(i-1, mask), (steps + 1, peop + (1<<i)))

        M = dp(k - 1, (1<<n) - 1)[1]
        return [i for i in range(k) if M & (1<<i) != 0]