LC 0698 [M] Partition to K Equal Sum Subsets - ALawliet/algorithms GitHub Wiki

The time complexity of the 2nd solution is actually O(2^ (k*n)), because if we have K trees stacked on top of each other, the new height of the tree is K * n.

O(k * 2^n) 2^n each for k subsets

I think that the worst time complexitiy is O(k*2^n). Because for each bucket, we have to check whether one specific subset of the nums array can be put into it. But as we have visited some of the numbers, and doing some optimization, like sorting the array or pruning, the time complexitiy will be much smaller than the worst case. Maybe we can get the average time complexity using the amortized analysis, but I have no idea.

if sums[j] == 0:
    break

This sentence is pure magic. Decrease the time from 2300ms to 30 ms!
Without this sentence, we are actually making each bucket unique.
However, it doesn't make sense because all buckets have the same size and they are the same.
If a single number couldn't fit into one bucket, it is a waste of time to put it into the other bucket.
adamzjk also mentioned the reason and it helps.

pass

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # TLE optimization
        if sum(nums) % k:
            return False
        nums.sort(reverse=True)
        
        target = sum(nums) / k
        used = [False] * len(nums)
        
        def backtrack(i, k, subsetSum):
            # print(i,k,subsetSum)
            if k == 0:
                return True
            if subsetSum == target:
                return backtrack(0, k - 1, 0)
            
            for i in range(start, len(nums)):
                if used[i] or subsetSum + nums[i] > target:
                    continue
                    
                used[i] = True
                if backtrack(i + 1, k, subsetSum + nums[i]):
                    return True
                used[i] = False

                # TLE optimization
                if subsetSum == 0:
                    break
            return False
    
        return backtrack(0, k, 0)

TLE

def canPartitionKSubsets(self, A, k):
        if len(A) < k:
            return False
        ASum = sum(A)
        A.sort(reverse=True)
        if ASum % k != 0:
            return False
        target = [ASum / k] * k

        def dfs(pos):
            if pos == len(A): return True

            for i in range(k):
                if target[i] >= A[pos]:

                    target[i] -= A[pos]
                    if dfs(pos + 1):
                        return True
                    target[i] += A[pos]

            return False
        return dfs(0)

pass

def canPartitionKSubsets(self, nums, k):
        sums = [0]*k
        subsum = sum(nums) / k
        nums.sort(reverse=True)
        l = len(nums)
        
        def walk(i):
            if i == l:
                return len(set(sums)) == 1

            for j in range(k):
                sums[j] += nums[i]
                if sums[j] <= subsum and walk(i+1):
                    return True
                sums[j] -= nums[i]

                if sums[j] == 0:
                    break
            return False        
        
        return walk(0)