Partition Equal Subset Sum

def canPartition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    reachable = [False] * (target + 1)
    reachable[0] = True
    for num in nums:
        for s in range(target, num - 1, -1):
            reachable[s] |= reachable[s - num]
    return reachable[target]

Partition Equal Subset Sum. Given an array of positive numbers, can you split it into two groups with equal sums? Every number goes on one side of the scale.

Take one, five, eleven and five: twenty-two in all, so each side needs eleven. Eleven alone balances one, five and five: true. But one, two, three and five total eleven, which is odd, so they can't split evenly: false.

The simple way: try every subset. Each number is in or out, so n numbers give two to the n subsets: exponential.

Instead, one side only needs to reach half the total: the target. That's a zero one knapsack. Keep a row of lamps, one per sum up to the target, with lamp zero lit. For each number, lamp s lights if lamp s minus that number is already lit.

In code: an odd total returns false. Otherwise, the target is half, and reachable starts with just zero. For each number, sweep the sums from the target down to the number: reachable of s, or reachable of s minus num. Return reachable of target. Why downward? Going up, the one would light lamp one, then lamp two from it: used twice.

Let's light them. One lights lamp one. Five lights six, then five. Eleven lights lamp eleven: the target! The last five adds ten. Lamp eleven is lit: true.

That's order n times target time, and one row of lamps: order target space.

Odd total, false. Otherwise, light sums up to half, sweeping down. That's Partition Equal Subset Sum.