Backtracking Target: 15s
Try placing each number into k buckets. Prune: skip if bucket overflows, skip symmetric bucket states.
def canPartitionKSubsets(nums, k):
total = sum(nums)
if total % k: return False
target = total // k
nums.sort(reverse=True)
buckets = [0] * k
def backtrack(i):
if i == len(nums): return all(b == target for b in buckets)
seen = set()
for j in range(k):
if buckets[j] + nums[i] > target: continue
if buckets[j] in seen: continue # prune symmetric
seen.add(buckets[j])
buckets[j] += nums[i]
if backtrack(i + 1): return True
buckets[j] -= nums[i]
return False
return backtrack(0)Type it from memory. Go.