Partition Equal Subset Sum: The 0/1 Knapsack in Disguise

"Given an array of positive integers, can it be split into two groups with equal sums?" It reads like a search over all ways to split the array, which would be 2^n of them. It is actually a small dynamic programming table, and once you see it, it is the 0/1 knapsack with the values removed.

The problem it solves

Split [3, 3, 4, 2] into two groups with the same total: 3 + 3 against 4 + 2, yes. [1, 2, 5]: the total is 8, but no group sums to 4, so no. The question only asks whether a split exists, and optionally which one.

The intuition

Two observations shrink the problem.

First, if the two groups have equal sums, each is exactly half the total. An odd total can never split, so return False at once. With an even total, the question becomes: is there a subset that sums to total / 2? The other group is automatically everything else.

Second, you do not need to remember which subsets exist, only which sums are reachable. Keep one boolean per sum from 0 to half. Before any number is used, only 0 is reachable: the empty subset. Each new number n then extends every sum that was already reachable: if s - n was reachable, s now is.

That is the 0/1 knapsack's table with the values thrown away. Each item can be taken at most once, and the capacity is half.

The one subtle line is the loop direction. Walking the sums from high to low means can[s - n] is always read before this same n could have set it, so each number is used once. Walking from low to high lets n build on a sum it just created, which silently turns the problem into "each number may be used any number of times".

Watch it run

The animation uses the crates 3, 3, 4, 2, total 12, target 6. It starts with only sum 0 lit, then shows each number lighting new sums from old ones: the first 3 lights 3, the second 3 lights 6. By the end sum 6 is lit, so the crates split 3 + 3 against 4 + 2, while sum 1 never lights, because no crate weighs one.

The code

The standard version, with an early exit once half is reachable:

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False                         # an odd total never splits evenly
    half = total // 2
    can = [True] + [False] * half            # can[s]: some subset sums to s
    for n in nums:
        for s in range(half, n - 1, -1):     # backwards: n is used at most once
            can[s] = can[s] or can[s - n]
        if can[half]:
            return True
    return can[half]

print(can_partition([3, 3, 4, 2]), can_partition([1, 2, 5]), can_partition([1, 5, 11, 5]))
# True False True

What the forwards loop gets wrong. With 1, it marks 1, then 2 from 1, then 3 from 2: one number reused as often as it likes:

def forwards_bug(nums):
    half = sum(nums) // 2
    can = [True] + [False] * half
    for n in nums:
        for s in range(n, half + 1):         # forwards: n can be reused
            can[s] = can[s] or can[s - n]
    return can[half]

print(forwards_bug([1, 2, 5]))               # True, but no subset of 1, 2, 5 sums to 4

The same table packed into one Python integer. Bit s is set when sum s is reachable, and shifting by n adds n to every reachable sum at once:

def can_partition_bits(nums):
    total = sum(nums)
    bits = 1                                 # only sum 0 is reachable
    for n in nums:
        bits |= bits << n
    return total % 2 == 0 and (bits >> (total // 2)) & 1 == 1

print(can_partition_bits([3, 3, 4, 2]), can_partition_bits([1, 2, 5]))   # True False

Recovering one valid half. Instead of a boolean, record the index of the number that first reached each sum, then walk back from half:

def one_half(nums):
    total = sum(nums)
    if total % 2:
        return None
    half = total // 2
    first = [None] * (half + 1)              # first[s]: index of the number that first reached s
    first[0] = -1
    for i, n in enumerate(nums):
        for s in range(half, n - 1, -1):
            if first[s] is None and first[s - n] is not None:
                first[s] = i
    if first[half] is None:
        return None
    picked, s = [], half
    while s:
        i = first[s]
        picked.append(nums[i])
        s -= nums[i]
    return picked

print(one_half([3, 3, 4, 2]), one_half([1, 5, 11, 5]))   # [3, 3] [11]

All three against a brute force that tries every subset, on 1,000 random arrays:

import itertools, random

def brute(nums):
    total = sum(nums)
    return any(2 * sum(c) == total
               for r in range(len(nums) + 1)
               for c in itertools.combinations(nums, r))

random.seed(15)
ok = True
for _ in range(1000):
    nums = [random.randint(1, 12) for _ in range(random.randint(1, 10))]
    want = brute(nums)
    ok &= can_partition(nums) == want == can_partition_bits(nums)
    half = one_half(nums)
    ok &= (half is not None) == want
    if half is not None:
        rest = list(nums)
        for x in half:
            rest.remove(x)                   # the picked numbers really come from nums
        ok &= sum(half) == sum(rest)
print(ok)                                    # True

The complexity

• Brute force looks at 2^n subsets, each costing up to O(n) to sum.
• The table does n passes over at most half + 1 sums: O(n * sum) time and O(sum) space. That is pseudo-polynomial: polynomial in the numeric value of the sum, not in the length of the input. Numbers in the millions make the table huge even for ten items.
• The bitset has the same asymptotic cost, but each shift-and-or handles every reachable sum in one big-integer operation instead of one Python loop step per sum.
• Recovery adds one array of the same size and an O(n) walk back.

Where it goes wrong

• Skipping the odd check. total // 2 floors, so [1, 2] would look for sum 1 and report a split that does not exist.
• Looping forwards. That is the unbounded knapsack, as shown above.
• Negative numbers. The table indexes by sum and assumes positive integers; negative values need an offset or a dictionary of reachable sums.
• The empty array. Its total is 0 and it splits trivially into two empty groups, so the code returns True; decide whether the problem allows that.

How to say it in an interview

"Two equal halves means one subset summing to exactly total / 2, so an odd total is an immediate no. Then it's subset sum: I keep a boolean per sum up to half, start with only zero reachable, and for each number mark s reachable if s - n was. I loop the sums downwards so each number is used once; forwards would reuse it. That's O(n * sum) time and O(sum) space, pseudo-polynomial. If they want the actual split, I store which number first reached each sum and walk back."

The table this is cut down from is the full 0/1 knapsack, and the forwards loop that goes wrong here is exactly right in the unbounded knapsack.