235. Partition Equal Subset Sum

Why this mechanism works

Equal halves must each sum to half the total, so an odd total is impossible. For an even total, the problem is zero-one subset-sum reachability. A boolean capacity table and descending updates ensure each occurrence is used at most once; the complement automatically forms the other half.

State and boundaries

reachable[s] means some subset of processed occurrences sums exactly to s. reachable[0] is always true via the empty subset.

Protocol

1. Compute total and reject odd parity.
2. Set target=total//2.
3. Initialize only sum zero reachable.
4. For each value update sums downward with reachable[s-value].
5. Return target reachability.

Visualization

[1,5,11,5], total 22, target 11
subset [11] and complement [1,5,5]
one reachable half is sufficient evidence

Python implementation

def equal_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    reachable = [False] * (target + 1)
    reachable[0] = True
    for value in nums:
        for amount in range(target, value - 1, -1):
            reachable[amount] = reachable[amount] or reachable[amount - value]
    return reachable[target]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 equal_partition: total = sum(nums)
nums=[1, 5, 11, 5]; total=22

L5 equal_partition: target = total // 2
nums=[1, 5, 11, 5]; total=22; target=11

L6 equal_partition: reachable = [False] * (target + 1)
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[False, False, False, False, False, False, False, False, ...]

L7 equal_partition: reachable[0] = True
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, False, False, False, False, False, False, False, ...]

L8 equal_partition: for value in nums:
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, False, False, False, False, False, False, False, ...]; value=1

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, False, False, False, False, False, False, False, ...]; value=1; amount=11

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, False, False, False, False, False, False, False, ...]; value=1; amount=10

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, False, False, False, False, False, False, False, ...]; value=1; amount=9

... 24 intermediate state changes omitted ...

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, True, False, False, False, True, True, False, ...]; value=5; amount=8

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, True, False, False, False, True, True, False, ...]; value=5; amount=7

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, True, False, False, False, True, True, False, ...]; value=5; amount=6

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 5, 11, 5]; total=22; target=11; reachable=[True, True, False, False, False, True, True, False, ...]; value=5; amount=5

L2 equal_partition: total = sum(nums)
nums=[1, 2, 5]; total=8

L5 equal_partition: target = total // 2
nums=[1, 2, 5]; total=8; target=4

L6 equal_partition: reachable = [False] * (target + 1)
nums=[1, 2, 5]; total=8; target=4; reachable=[False, False, False, False, False]

L7 equal_partition: reachable[0] = True
nums=[1, 2, 5]; total=8; target=4; reachable=[True, False, False, False, False]

L8 equal_partition: for value in nums:
nums=[1, 2, 5]; total=8; target=4; reachable=[True, False, False, False, False]; value=1

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 2, 5]; total=8; target=4; reachable=[True, False, False, False, False]; value=1; amount=4

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 2, 5]; total=8; target=4; reachable=[True, False, False, False, False]; value=1; amount=3

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 2, 5]; total=8; target=4; reachable=[True, False, False, False, False]; value=1; amount=2

... 5 intermediate state changes omitted ...

L10 equal_partition: reachable[amount] = reachable[amount] or reachable[amount - value]
nums=[1, 2, 5]; total=8; target=4; reachable=[True, True, False, True, False]; value=2; amount=3

L9 equal_partition: for amount in range(target, value - 1, -1):
nums=[1, 2, 5]; total=8; target=4; reachable=[True, True, False, True, False]; value=2; amount=2

L10 equal_partition: reachable[amount] = reachable[amount] or reachable[amount - value]
nums=[1, 2, 5]; total=8; target=4; reachable=[True, True, True, True, False]; value=2; amount=2

L8 equal_partition: for value in nums:
nums=[1, 2, 5]; total=8; target=4; reachable=[True, True, True, True, False]; value=5; amount=2

Why the solution is correct

Any equal partition supplies a subset of sum total/2, and any such subset leaves a complement of the same sum. Each update either skips the occurrence or includes it once using an earlier-layer sum, so reachable tracks exactly all possible subset sums.

Time and space

O(n*T) time and O(T) auxiliary storage for target T=total/2; pseudopolynomial in the numeric sum.

Common mistakes

Ascending sums can reuse an occurrence. Negative input values invalidate the nonnegative bounded-capacity representation.

Reasoning card

Transfer exercise

Use a bitset with bits |= bits<<value to represent reachable sums, then explain why the whole shift reads the old bitset.