Dynamic Programming: Knapsack - Partition to K Equal Sum Subsets
The following code attempts to solve the Partition to K Equal Sum Subsets problem using DP with bitmask tabulation. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.
def canPartitionKSubsets(nums, k):
total = sum(nums)
if total % k != 0:
return False
target = total // k
n = len(nums)
nums.sort()
if nums[-1] > target:
return False
dp = [-1] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == -1:
continue
for i in range(n):
if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
next_mask = mask | (1 << i)
dp[next_mask] = (dp[mask] + nums[i]) % target
return dp[(1 << n) - 1] == 0