Dynamic Programming: Knapsack - Partition to K Equal Sum Subsets
Consider the following Python function implementing the DP with bitmask tabulation approach for partitioning an array into k equal sum subsets. What is the return value when called with
nums = [1, 2, 3, 4] and k = 2?
from typing import List
def canPartitionKSubsets(nums: List[int], k: int) -> bool:
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)
if dp[next_mask] == -1:
dp[next_mask] = (dp[mask] + nums[i]) % target
return dp[(1 << n) - 1] == 0
