Problem statement

https://binarysearch.com/problems/K-Partitionable-List/

Solution

Equal to Leetcode 0698. Partition to K Equal Sum Subsets. Just one small difference that bucket size can be equal to 0.

Complexity

Overall time complexity is O(2^n*n) and space complexity is O(2^n).

Code

class Solution:
    def solve(self, nums, k):
        N = len(nums)
        nums.sort(reverse = True)

        basket, rem = divmod(sum(nums), k)
        if rem or nums[0] > basket: return False

        dp = [-1] * (1<<N) 
        dp[0] = 0
        for mask in range(1<<N):
            for j in range(N):
                neib = dp[mask ^ (1<<j)]
                if mask & (1<<j) and neib >= 0 and neib + nums[j] <= basket:
                    dp[mask] = (neib + nums[j]) % (basket if basket != 0 else float("inf"))
                    break

        return dp[-1] == 0