DSA Partition Equal Subset Sum

The problem

Partition Equal Subset asks whether a list of positive whole numbers can split into two groups with equal sums. Every value goes into exactly one group. The two groups together use the whole list.

If a split exists, each group sums to half of the total. The problem is therefore a search for one group that sums to exactly half. The other group is whatever remains.

cases = [
    ([1, 5, 11, 5], True),
    ([1, 2, 3, 5], False),
    ([1, 2, 5], False),
    ([3, 3, 3, 4, 5], True),
    ([4], False),
]
for nums, expected in cases:
    print("values", nums, "total", sum(nums), "can partition:", expected)

The second list totals 11, an odd number. No split into two equal whole sums can exist for it. The other rows need the search.

Intuition: grabbing the largest that fits fails

The first idea builds one group greedily. It considers values from largest to smallest and takes each one that still fits under the target. It never undoes a choice.

nums = [2, 3, 4, 5, 7, 9]
target = sum(nums) // 2
group = []
for value in sorted(nums, reverse=True):
    if sum(group) + value <= target:
        group.append(value)
print("target:", target)
print("greedy group:", group, "sum:", sum(group))
print("working group:", [7, 5, 3], "sum:", 7 + 5 + 3)

The greedy group stalls at 14. It took 9 and then 5, and no remaining value is 1. A different group, 7 + 5 + 3, reaches 15 exactly. The search must consider leaving a large value out.

Brute force: test every subset

The brute force lists every subset of the values. It sums each subset in full. A subset that sums to the target settles the question.

nums = [1, 5, 11, 5]
target = sum(nums) // 2
checked = 0
found = None
for mask in range(2 ** len(nums)):
    checked += 1
    group = [nums[i] for i in range(len(nums)) if mask & (1 << i)]
    if sum(group) == target and found is None:
        found = group
print("target:", target)
print("subsets checked:", checked)
print("one working group:", found)

Four values give 16 subsets. Each added value doubles the subset count. The brute force also sums many subsets that have already passed the target and can never come back.

The optimal solution: track every reachable sum

The state is the set of sums that some group of the values seen so far can reach. That one sentence is the whole method.

An odd total fails before the search starts. For an even total the target is half of it. Each value is added to every sum reached before it, once, and sums past the target are dropped.

def can_partition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    reachable = {0}
    for value in nums:
        reachable = reachable | {s + value for s in reachable if s + value <= target}
    return target in reachable

cases = [
    ([1, 5, 11, 5], True),
    ([1, 2, 3, 5], False),
    ([1, 2, 5], False),
    ([3, 3, 3, 4, 5], True),
    ([4], False),
]
for nums, expected in cases:
    result = can_partition(nums)
    print("values", nums, "->", result, "expected:", expected, "match:", result == expected)

All five cases match. The target enters the reachable set exactly when a split exists. Each value enters each sum at most once, because the new sums are built from the set as it stood before that value.

Walkthrough: reachable sums for [1, 5, 11, 5]

The total is 22, so the target is 11. The walk adds one value at a time. Each line prints the reachable sums up to the target, sorted, after that value joins.

nums = [1, 5, 11, 5]
target = sum(nums) // 2
reachable = {0}
print("start:", sorted(reachable))
for value in nums:
    reachable = reachable | {s + value for s in reachable if s + value <= target}
    print("after", value, ":", sorted(reachable))
print("target", target, "reachable:", target in reachable)

The value 11 puts the target itself into the set. A split exists from that step on. One group is 11 alone, and the other group is 1 + 5 + 5.

Complexity

Time is O(n times target), where n is the count of values. Each value is added to each reachable sum once, and no stored sum passes the target.

Space is O(target). The set holds at most one entry per sum from 0 to the target.

for n in [4, 8, 12]:
    print("values", n, "- brute subsets:", 2 ** n)

def count_additions(nums):
    target = sum(nums) // 2
    reachable = {0}
    additions = 0
    for value in nums:
        additions += len(reachable)
        reachable = reachable | {s + value for s in reachable if s + value <= target}
    return additions

print("additions for [1, 5, 11, 5]:", count_additions([1, 5, 11, 5]))
print("additions for eight values:", count_additions([1, 2, 3, 4, 5, 6, 7, 8]))

Subset counts double with each added value. Reachable additions grow with the target instead. The target is a sum of values, not a count of them, so a list of large values costs more than a list of small ones.

Edge cases and pitfalls

An empty list totals 0, and two empty groups have equal sums, so it answers True. A single value can never split, because its half is smaller than the value itself and no group reaches it.

def can_partition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    reachable = {0}
    for value in nums:
        reachable = reachable | {s + value for s in reachable if s + value <= target}
    return target in reachable

print("empty list:", can_partition([]))
print("single value:", can_partition([4]))
print("pair of equals:", can_partition([2, 2]))
print("one huge value:", can_partition([100, 1, 1]))

The classic bug builds the new sums from the set that is already growing. One value then feeds its own new sums and gets used many times in a single step.

reachable = {0}
value = 3
new_sums = {s + value for s in reachable}
reachable = reachable | new_sums
print("after one pass with a single 3:", sorted(reachable))
new_sums = {s + value for s in reachable}
reachable = reachable | new_sums
print("after a mistaken second pass:", sorted(reachable))
print("6 claimed from one 3:", 6 in reachable)

The second pass is the bug in disguise. Building every new sum from the set as it stood before the value keeps each value single-use. That rule turns the reachable set into a packing method, and the next lessons name that shape directly.