Partition Equal Subset Sum

Signal

"Can a subset hit an exact target" — equal-partition is just subset-sum in disguise: if the total is even, the question becomes "is there a subset summing to exactly half the total".

Approach

If the total sum is odd, an equal split is impossible immediately. Otherwise, the target is total // 2. Track which sums are reachable using a boolean array of size target + 1, seeded with dp[0] = True (an empty subset sums to 0). For each number, update reachability for sums downward from target to that number — going downward stops a single number from being counted twice within the same pass.

Skeleton

if total % 2: return False
target = total // 2
dp = [True] + [False] * target
for x in nums:
    for s in range(target, x - 1, -1):
        dp[s] = dp[s] or dp[s - x]
return dp[target]

Solution

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False

    target = total // 2
    dp = [True] + [False] * target

    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]

    return dp[target]

Complexity

O(n · target) time, O(target) space — target is sum(nums) // 2, so this is pseudo-polynomial (depends on the value of the sum, not just n).

Pitfalls

• Iterating the inner sum loop upward instead of downward lets a single number be used more than once in forming the same target — this is the 0/1-knapsack "each item once" pattern, and direction is how that constraint is enforced without extra bookkeeping.
• Skipping the odd-total short-circuit and running the DP anyway still gives the right answer but wastes the full O(n · target) pass on a question answerable in O(n).
• This is a decision problem ("can you"), not "how many ways" — don't accidentally sum booleans or counts where a plain or is all that's needed.