9.13
Idea: if the total sum S of the multiset is not divisible by k, no solution exists. Otherwise every subset has to sum to T = S∕k. A depth-first search that always puts the next largest element into the first bucket in which it fits, together with memoisation of already explored states, solves the problem efficiently in practice.
Pseudocode (indices 0 … n-1, numbers sorted descending):
function canPartition(nums, k):
S ← sum(nums)
if S mod k ≠ 0: return false
target ← S / k
buckets ← array[k] filled with 0
used ← bitmask 0
memo ← empty set
function dfs(idx, buckets, used):
if idx = len(nums): return true // all placed
if (used) in memo: return false // state seen
for i in 0 … k-1:
if buckets[i] + nums[idx] ≤ target:
buckets[i] += nums[idx]
if dfs(idx+1, buckets, used | (1 « idx)): return true
buckets[i] -= nums[idx]
if buckets[i] = 0: break // symmetry pruning
memo.add(used)
return false
return dfs(0, buckets, used)
Python implementation:
def k_partition(nums, k):
nums.sort(reverse=True)
s = sum(nums)
if s % k: return False
target = s // k
buckets = [0]*k
memo = set()
def dfs(idx):
if idx == len(nums):
return True
state = tuple(sorted(buckets)) # small memo key
if (idx, state) in memo:
return False
for i in range(k):
if buckets[i] + nums[idx] <= target:
buckets[i] += nums[idx]
if dfs(idx+1):
return True
buckets[i] -= nums[idx]
if buckets[i] == 0:
break
memo.add((idx, state))
return False
return dfs(0)
Correctness sketch: 1) Feasibility check guarantees a necessary condition. 2) The DFS explores every assignment of items to buckets that respects the capacity
T; pruning rules do not remove any viable solution because (a) symmetry pruning only skips permutations of empty buckets, and (b) memoisation merely skips states already fully processed. Hence if a solution exists it will be found.Complexity: Let n be the number of items. In the worst case DFS enumerates up to kⁿ states. With the two pruning rules the average running time is dramatically lower and handles typical inputs up to 16–20 numbers in milliseconds.
Usage example:
>>> k_partition([4,3,2,3,5,2,1], 4) → True (because {5},{1,4},{2,3},{2,3}).
Back to
Chapter 9
