Partition Equal Subset Sum

Partition Equal Subset Sum asks whether an array can be split into two groups with the same total. It looks like a "try all combinations" problem, but it is really a classic 0/1 knapsack in disguise — and a single boolean array solves it fast.

The slow way first

The brute-force idea: try every possible subset and check if its sum equals half the total. With n elements there are 2ⁿ subsets, so this is O(2ⁿ) — hopeless for anything but tiny arrays.

The reframe that unlocks it: if the total is S, the two halves each need to sum to S / 2. So the real question is just can any subset reach exactly target = S / 2? If S is odd, no split is possible and we can answer false immediately.

The idea: track which sums are reachable

Keep a boolean array dp where dp[t] means "some subset reaches sum t". Start with dp[0] = True (the empty subset sums to 0). Then fold in each number one at a time: a number num lets us reach any sum t whose remainder t - num was already reachable, so dp[t] = dp[t] or dp[t - num].

The one subtlety: iterate t from target downward to num. Going downward means each number is used at most once per sum — if we went upward, dp[t - num] could already include num from this same pass, letting us reuse an element.

Walk through it

Step through the animation. The dp row starts with only dp[0] True. As we fold in 1, then 5, then 11, more sums light up. The moment we process 11, dp[11] = dp[0] flips True — the target is reachable, so the answer is yes.

Pseudocode

total = sum(nums)
if total is odd:                 # cannot split an odd total evenly
    return false
target = total / 2
dp = array of False, size target+1
dp[0] = true                     # empty subset reaches sum 0
for each num in nums:
    for t from target down to num:
        dp[t] = dp[t] or dp[t - num]
return dp[target]

The Python solution

def can_partition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for num in nums:
        for t in range(target, num - 1, -1):
            dp[t] = dp[t] or dp[t - num]
    return dp[target]

• total = sum(nums); if it is odd, no equal split exists, so we bail out early.
• target = total // 2 is the sum each subset must hit.
• dp[0] is True (empty subset), every other entry starts False.
• The outer loop folds in one num at a time — each element gets one chance to be used.
• The inner loop goes downward (target → num) so each num is counted at most once per sum.
• dp[t] = dp[t] or dp[t - num] says: t is reachable if it already was, or if t - num was.
• The answer is dp[target] — did any subset hit exactly half the total?

Complexity

We trade a one-dimensional boolean array (O(target) space) for an enormous speed win: exponential down to pseudo-polynomial O(n × target). This is the standard 0/1 knapsack shape — one item dimension, one capacity dimension.

When this pattern shows up

Practice