Partition Equal Subset Sum

Intuition

If the two subsets must have equal sums, then each must equal half of the total, so the total has to be even to begin with. Once we know the target is total/2, the question becomes: can any subset of the numbers add up to that target? This is the classic 0/1 subset-sum problem. We track which sums are reachable using a boolean array, and each number may be used at most once. By iterating the sums from high to low we guarantee each number contributes to any given sum only a single time.

Algorithm walkthrough

1. 1Compute the total sum; if it is odd, return false immediately because no equal integer split can exist.
2. 2Set target = total / 2 and create a boolean array reachable of size target + 1 with reachable[0] = true.
3. 3For each number, iterate s from target down to the number and mark reachable[s] true when reachable[s - num] is true.
4. 4Iterating downward is essential: it prevents a single number from being counted more than once toward the same sum.
5. 5After processing all numbers, return reachable[target], which tells whether a subset summing to half the total exists.

Implementation

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        reachable = [False] * (target + 1)
        reachable[0] = True
        for num in nums:
            for s in range(target, num - 1, -1):
                if reachable[s - num]:
                    reachable[s] = True
        return reachable[target]