DSA Partition into K Equal Subsets

The problem

Partition into K Equal Subsets asks whether a list can be split into k groups with the same sum. Every value is used exactly once. The groups are unlabeled, so swapping two whole groups changes nothing.

The answer in this article is True or False. The target sum is the total divided by k. A split is impossible at once when that division leaves a remainder.

cases = [([4, 3, 2, 3, 5, 2, 1], 4), ([5, 5, 4, 4, 3, 3, 2, 2], 4), ([3, 3, 3, 5, 5, 5], 4)]
for nums, k in cases:
    total = sum(nums)
    print(nums, 'k =', k, 'total:', total, 'divides evenly:', total % k == 0, 'target:', total // k if total % k == 0 else None)

All three totals divide by four. The first two lists split, and the third does not. Divisibility is a necessary check, and the third case shows it is not a sufficient one.

Intuition: fill each group in the order given

The first idea walks the values in their given order. It puts each value into the first group that still has room. The idea never moves a value once placed.

That greed is the trap. An early placement can strand a later large value with no room in any group. A search that can undo placements recovers from that mistake, and the greedy walk cannot.

nums = [2, 2, 3, 3, 4, 4]
k = 3
target = sum(nums) // k
buckets = [0] * k
stuck = None
for value in nums:
    placed = False
    for b in range(k):
        if buckets[b] + value <= target:
            buckets[b] += value
            placed = True
            break
    if not placed:
        stuck = value
        break
print('target:', target)
print('buckets when stuck:', buckets)
print('stuck value:', stuck)
print('a valid split exists: [4, 2], [4, 2], [3, 3]')

The greedy fill strands the last 4 with every bucket unable to take it. A valid split exists for the same values, pairing each 4 with a 2 and the two 3s together. A search that can undo a placement recovers from the early choices, and the greedy walk cannot.

Brute force: try every assignment of values to buckets

The brute force assigns each value to one of the k buckets in every possible way. It checks the bucket sums only after every value is placed. A counter records the assignments built.

import itertools
def brute(nums, k):
    target = sum(nums) // k
    built = [0]
    for assign in itertools.product(range(k), repeat=len(nums)):
        built[0] += 1
        buckets = [0] * k
        for value, b in zip(nums, assign):
            buckets[b] += value
        if all(x == target for x in buckets):
            return True, built[0]
    return False, built[0]
result, built = brute([2, 2, 2, 2], 2)
print('values [2, 2, 2, 2] k = 2 possible:', result, 'assignments built:', built)
result, built = brute([3, 1, 2], 2)
print('values [3, 1, 2] k = 2 possible:', result, 'assignments built:', built)

Four values into two buckets have 16 assignments in total, and each added value multiplies that total by k. The counter shows the search stopping at the first valid assignment it builds. The optimal search prunes a bucket the moment its sum passes the target, and it never builds the dead assignments at all.

The optimal solution: largest first, with symmetric buckets skipped

The search tries values in descending order, largest first, and a value is placed only in a bucket whose sum stays at or below the target, with later empty buckets skipped as repeats of the first empty one. That one sentence is the whole method.

A value larger than the target ends the search at once. Empty buckets are interchangeable, so only the first empty bucket is tried for each value. Skipping the later empty buckets is counted each time it happens.

def can_partition(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False, 0, 0
    target = total // k
    ordered = sorted(nums, reverse=True)
    if ordered[0] > target:
        return False, 0, 0
    buckets = [0] * k
    calls = [0]
    skips = [0]
    def search(index):
        calls[0] += 1
        if index == len(ordered):
            return True
        value = ordered[index]
        seen_empty = False
        for b in range(k):
            if buckets[b] + value > target:
                continue
            if buckets[b] == 0 and seen_empty:
                skips[0] += 1
                continue
            if buckets[b] == 0:
                seen_empty = True
            buckets[b] += value
            if search(index + 1):
                return True
            buckets[b] -= value
        return False
    result = search(0)
    return result, calls[0], skips[0]
cases = [([4, 3, 2, 3, 5, 2, 1], 4), ([5, 5, 4, 4, 3, 3, 2, 2], 4), ([3, 3, 3, 5, 5, 5], 4)]
for nums, k in cases:
    result, calls, skips = can_partition(nums, k)
    print(nums, 'k =', k, 'possible:', result, 'calls:', calls, 'empty skips:', skips)

Every case from the start of the article is answered. The impossible case finishes in 6 calls with 6 empty-bucket skips. Without the skip, that same case explores far more symmetric branches for the same answer.

Walkthrough: building the groups for the first case

The walk follows the successful placements for the first case. The target is 5. Each step adds one value, largest first, to one bucket.

ordered = [5, 4, 3, 3, 2, 2, 1]
placements = [(5, 0), (4, 1), (3, 2), (3, 3), (2, 2), (2, 3), (1, 1)]
buckets = [0, 0, 0, 0]
for value, b in placements:
    buckets[b] += value
    print('place', value, 'in bucket', b, 'buckets:', list(buckets))
print('all buckets at target 5:', all(x == 5 for x in buckets))

The last placement fills the last bucket to 5. All four buckets hold 5 at that point. That state is the split, read straight off the buckets.

Complexity

The brute force builds k to the power n assignments for n values. The pruned search still has an exponential worst case, because a bucket sum can stay legal down many branches, but the target prune and the empty-bucket skip cut the explored branches sharply in practice.

The extra space is the bucket list of length k plus the recursion depth of n. The ordered copy of the values takes O(n) space.

print('impossible case calls with skip: 6')
print('empty skips counted: 6')
print('brute assignments for 6 values, 4 buckets:', 4 ** 6)

Counts beat clocks here. The pruned search answers the impossible case in single-digit calls. The brute force would build 4096 assignments for a list of that shape.

Edge cases and pitfalls

A total that does not divide by k answers False with no search at all. A single value above the target also answers False at once. Both checks run before any bucket is touched.

Trying every empty bucket is the classic waste. Empty buckets are identical, so each extra empty try repeats a search already done. The skip is a correctness-neutral cut, and removing it changes the call count, never the answer.

def early_verdict(nums, k):
    total = sum(nums)
    if total % k != 0:
        return 'impossible: total does not divide by k'
    target = total // k
    if nums and max(nums) > target:
        return 'impossible: a value passes the target'
    return 'passes both early checks, target ' + str(target)
print('total not divisible:', early_verdict([1, 2, 4], 2))
print('value above target:', early_verdict([10, 1, 1], 2))
print('clean case:', early_verdict([4, 3, 2, 3, 5, 2, 1], 4))
print('empty list:', early_verdict([], 3))

The first two cases are settled by the early checks alone. An empty list has total zero, which divides evenly, and its split is the trivial one of empty groups. The clean case passes both checks and goes on to the search, which finds its split.