Leetcode: 1723. Find Minimum Time to Finish All Jobs

Mistake: Did not consider different approaches and got stuck on the Dynamic Programming solution.
Pattern: Find optimal subset of small set. Use Brute Force to assign each job to a worker and prune the search with the current maximum working time for the updated job. To make the search faster, sort the input in decreasing order.
Can we use brute-force to solve the problem? The most important prune is to make sure that a job is assigned as the first job of a work only once. Time complexity is \(O(n^k)\) but the prunes makes the solution faster than Dynamic Programming.

from typing import List


class Solution:
    def minimumTimeRequired(self, jobs: List[int], K: int) -> int:
        N = len(jobs)
        jobs.sort(reverse=True)
        load = [0] * N
        ans = float("inf")

        def bt(i, cur):
            nonlocal ans
            if cur >= ans:
                return
            if i == N:
                ans = min(ans, cur)
                return
            for j in range(K):
                load[j] += jobs[i]
                if load[j] < ans:
                    bt(i + 1, max(cur, load[j]))
                load[j] -= jobs[i]
                if load[j] == 0:
                    break

        bt(0, 0)
        return ans


assert Solution().minimumTimeRequired([3, 2, 3], 3) == 3
assert Solution().minimumTimeRequired([1, 2, 4, 7, 8], 2) == 11

How can we extend the solution for \(i\) to \(i+1\)? The search-space is defined by \((k, S)\) where \(k\) is the number of workers used so far and \(S\) represents the completed jobs. Time and space complexity is \(O(k \times 2^n)\).

from typing import List


class Solution:
    def minimumTimeRequired(self, jobs: List[int], K: int) -> int:
        S = sum(jobs)
        N = len(jobs)
        M = 2**N

        cost = [0] * M
        for i in range(M):
            for j in range(N):
                if i & (1 << j):
                    cost[i] += jobs[j]

        def submasks(mask):
            submask = mask
            while submask:
                yield submask
                submask = (submask - 1) & mask

        dp = [[float("inf")] * M for _ in range(K + 1)]
        for k in range(K, -1, -1):
            if k == K:
                dp[k][M - 1] = 0
            else:
                for used in range(M):
                    allowed = (M - 1) ^ used
                    cur = float("inf")
                    for new in submasks(allowed):
                        if cost[new] < cur:
                            cur = min(cur, max(cost[new], dp[k + 1][used | new]))
                    dp[k][used] = cur
        return dp[0][0]


assert Solution().minimumTimeRequired([3, 2, 3], 3) == 3
assert Solution().minimumTimeRequired([1, 2, 4, 7, 8], 2) == 11