Partition into K Buckets

Some problems ask you to split every item into k groups: k subsets with equal sums, four equal sides of a square, cookies shared between k children. The search space is huge (each item could go in any of k buckets), so most of the work is pruning. The strongest prune comes from noticing that all empty buckets are identical.

The idea#

Start with the rule that shapes everything else: every element must be used. Then:

If sum(nums) % k != 0, the answer is False immediately. Otherwise each bucket must reach target = sum // k.
Fill one bucket at a time. Pick unused items for the current bucket until it hits the target.
When it's full, start the next bucket from index 0 with k - 1 buckets left.
When no buckets are left, every item is placed: return True.

The stranded-number prune#

Suppose you're starting an empty bucket, you put item x in it, and the search fails. Should you try starting the bucket with a different item instead?

No. x still has to go somewhere, and every remaining bucket is also empty, so each one is identical to this one. You have proved that x can't complete an empty bucket with the items left. It will be stranded with nowhere to go, so the whole branch is dead: return False straight away.

In the loop, that is one check right after the undo: if the current bucket sum is 0, return False.

Why sort descending#

The prune saves the most when it fires early, and the order of the items decides when that happens. Placing big items first makes failures happen early, near the root of the tree, where pruning saves the most. A big awkward item is also exactly the kind that gets stranded, so the prune fires sooner.

Complexity#

Naively each of N items picks one of k buckets: $O(k^N)$ . Filling bucket by bucket with the prunes is much faster in practice, but still exponential in the worst case.

How to spot it#

These cues point to bucket partitioning.

"Partition into k subsets with equal sum", "form a square from all matchsticks".
"Distribute all items among k people" to minimize the maximum load.
Small N (about 16 or less) and small k.
The word all: every item must be placed.

Template#

The template puts the pieces together: the divisibility check, the descending sort, bucket-by-bucket filling, and the stranded-number prune as one line after the undo.

if total % k != 0: return False
target = total // k
sort items descending                  # big items first: fail early
track(start, buckets_left, curr_sum):
    if buckets_left == 0: return True
    if curr_sum == target:             # bucket full: start the next one
        return track(0, buckets_left - 1, 0)
    for i from start to n - 1:
        if used[i] or curr_sum + items[i] > target: continue
        mark i used
        if track(i + 1, buckets_left, curr_sum + items[i]): return True
        unmark i
        if curr_sum == 0: return False # items[i] can't start any empty bucket
    return False
return track(0, k, 0)

To see the prune fire, trace the template on [4, 3, 3] with k = 2 and target 5.

Step	Bucket 1	Left	What happens
1	4	3, 3	needs 1 more, but no item is 1: fail
2	empty again	4, 3, 3	undo 4; `curr_sum == 0`, so return False

Without the prune, the loop would go on to start bucket 1 with a 3. That can't help: 4 must still go into bucket 2, an empty bucket of size 5 exactly like the one it failed to fill.

Worth exploring: memoizing this search on a bitmask of used items, which caps it at $2^N$ states and is the bridge from backtracking to DP.

Pitfalls#

Each of these costs you either a wrong answer or a timeout.

Not using every element. The problem says all items must be placed; a solution that leaves some out is wrong.
Sorting ascending. It's correct but much slower: failures surface deep in the tree.
Misplacing the prune. The curr_sum == 0 check belongs inside the loop, right after the undo.
Skipping the divisibility check. sum % k != 0 answers False instantly.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Partition to K Equal Sum Subsets.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Partition to K Equal Sum Subsets

This is the template as it stands. Check divisibility, sort descending, and fill one bucket at a time. The stranded-number prune is what keeps it fast.

Hint: Matchsticks to Square

The four sides are four buckets, so this is the same search with k = 4. Sort descending here too; it makes a large difference in speed.

Hint: Fair Distribution of Cookies

Items don't have to balance exactly. You minimize the largest total any child gets. Assign each cookie, in order, to one of the k children, and take the best result. Track how many children still have zero cookies: if n - index < zero_count, some child will end up with nothing, so the branch is invalid.

Hint: Partition Equal Subset Sum

With k = 2 you only need one subset with half the total. That's a subset-sum problem, and with larger inputs DP beats backtracking; see 0/1 Knapsack.

Key takeaways#

Check sum % k first; every bucket must reach sum // k.
Fill one bucket at a time and restart from index 0 when it's full.
Stranded-number rule: if an item fails to start an empty bucket, it fails for every empty bucket, so return False.
Sort descending so failures happen near the root.
Naive assignment is $O(k^N)$ ; the prunes are what make it pass.

Core idea#

Split every item into k groups with equal sums. Fill one bucket at a time, and prune hard, because all empty buckets are identical.

Key points#

Every element must be used.
If sum(nums) % k != 0, return False. Otherwise each bucket must reach target = sum // k.
When a bucket is full, start the next bucket from index 0 with k - 1 buckets left.
Stranded-number rule: if item x fails to start an empty bucket, it fails for every empty bucket. Return False.
In code, the rule is if curr == 0: return False, right after the undo.
Sort descending. Big items fail early, near the root, where pruning saves the most.
Naive assignment is $O(k^N)$ . The prunes make it pass, but it stays exponential.
Spot it: "k subsets with equal sum", "square from all matchsticks", N about 16 or less.

Variations#

Problem	Change
Matchsticks to Square	Same code with k = 4
Fair Distribution of Cookies	Minimize the largest bucket; prune when `n - index < zero_count`
k = 2	Subset sum with half the total; DP beats backtracking

Template#

if total % k != 0: return False
target = total // k; sort items descending
track(start, left, curr):
    if left == 0: return True
    if curr == target: return track(0, left - 1, 0)
    for i from start to n - 1:
        if used[i] or curr + items[i] > target: continue
        mark i used
        if track(i + 1, left, curr + items[i]): return True
        unmark i
        if curr == 0: return False     # stranded number
    return False

Pitfalls#

Leaving some items out of the buckets.
Sorting ascending. It is correct but much slower.
Placing the curr == 0 check outside the loop.
Skipping the divisibility check.

Say it in an interview#

"Fill one bucket at a time and restart from index 0 when it is full."
"If an item cannot start an empty bucket, no empty bucket can take it."