Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is an array of positive integers. The task is to decide whether the array can be split into two subsets whose sums are exactly equal.

The important simplification is that the two subset sums must each be half of the total sum. If the total sum is odd, the answer is immediately False because an odd number cannot be split into two equal integer sums. If the total sum is even, the whole problem becomes:

can any subset add up to total_sum // 2?

Once one subset reaches that target, the remaining numbers automatically form the other subset with the same sum.

The subset-sum reduction

This is a 0/1 subset-sum problem. Each number can be used either once or not at all. That detail matters: this is not like coin change, where the same value can be reused repeatedly.

Define reachable[s] as:

whether some subset of the numbers processed so far can make sum s

The starting state is reachable[0] = True, because choosing no numbers makes sum zero. For each number, update the sums it can newly create. If sum s - number was already reachable before using this number, then sum s becomes reachable after using it.

The key implementation detail is to scan sums backward from target down to number. Backward scanning prevents the same number from being used twice during one iteration. Forward scanning would accidentally turn this into an unbounded knapsack transition.

How to derive it in an interview

Start with the equal-sum observation. If the interviewer asks for two subsets with equal sums, do not try to construct both subsets independently. First compute the total. If it is odd, stop. If it is even, look for one subset whose sum is half of the total.

Then frame the state around reachability rather than around the subsets themselves. For every number, the choice is binary: skip it or take it. That gives the recurrence:

reachable_after[s] = reachable_before[s] or reachable_before[s - number]

A two-dimensional table over index and sum is easy to explain, but it stores more than needed. Each row only depends on the previous row, so it can be compressed to one array. The backward loop is what preserves the “previous row” behavior inside that one array.

Why the algorithm is correct

After processing some prefix of the array, reachable[s] is true exactly when a subset of that prefix can sum to s.

The invariant is true at the beginning because only sum zero is reachable with no chosen numbers. When a new number is processed, every old reachable sum remains reachable by skipping the number. Also, every sum s becomes reachable if s - number was reachable before, because adding the new number to that earlier subset creates s.

The backward scan makes sure s - number is read from the state before the current number was added, so each input value is used at most once. By induction, after all numbers are processed, reachable[target] tells exactly whether a subset can make half the total. If it can, the rest of the array has the same sum, so the array can be partitioned.

Python solution

from typing import List, Optional


def equal_partition_target(numbers: List[int]) -> Optional[int]:
    """Return the required subset sum, or None when equal partition is impossible."""
    total_sum = sum(numbers)
    if total_sum % 2 != 0:
        return None
    return total_sum // 2


def can_build_subset_sum(numbers: List[int], target_sum: int) -> bool:
    """Return whether a 0/1 subset of numbers can add up to target_sum."""
    reachable = [False] * (target_sum + 1)
    reachable[0] = True

    for number in numbers:
        if number == target_sum:
            return True

        if number > target_sum:
            return False

        # Traverse backward so the current number is used at most once.
        for current_sum in range(target_sum, number - 1, -1):
            if reachable[current_sum - number]:
                reachable[current_sum] = True

        if reachable[target_sum]:
            return True

    return reachable[target_sum]


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target_sum = equal_partition_target(nums)
        if target_sum is None:
            return False

        return can_build_subset_sum(nums, target_sum)

The time complexity is O(n * target), where target = total_sum // 2. The space complexity is O(target) for the reachability array. This is pseudo-polynomial time: it depends on the numeric sum, not only on the number of elements.

Interview follow-ups

Can you recover the actual subset, not just return true or false?

Yes. Store predecessor information when a sum first becomes reachable. For each newly reached sum s, remember that it came from s - number by taking number. After the DP finishes, walk backward from target through those predecessor links to reconstruct one valid subset.

This works because the same reachability transition already proves that every recorded predecessor is valid. The tradeoff is extra bookkeeping and O(target) additional storage for parents. The asymptotic time remains O(n * target), but the implementation needs to avoid overwriting parent choices in a way that makes reconstruction ambiguous.

What if the interviewer asks for the number of valid partitions?

The state changes from boolean reachability to counting. Instead of asking whether sum s can be made, store how many subsets can make sum s. For each number, scan backward and add count[s - number] into count[s].

The backward direction is still required because each number can be used once. The complexity remains O(n * target) time and O(target) space. One subtle point is that counting subsets that reach half the total may double-count full partitions, because choosing subset A versus subset B represents the same split. If the problem asks for unordered partitions, divide the final subset count by two.

Can this be optimized with a bitset?

Yes. Treat reachable sums as bits in an integer. Initially only bit zero is set. For each number, shift the bitset left by that number and OR it back into the original bitset. After all numbers are processed, check whether the target bit is set.

Conceptually, this is the same DP transition, but many sums are updated in one machine-level operation. In Python, this is often much faster and uses compact memory. The tradeoff is that it is less explicit in interviews and harder to extend when the interviewer asks for reconstruction or counting.

What changes if the array can contain negative numbers?

The simple one-dimensional array no longer works directly because reachable sums are no longer limited to 0..target. One approach is to track reachable sums in a set: start with {0}, and for each number add both the old sums and old_sum + number.

That handles negatives naturally, but it can grow to many distinct sums. Another option is to offset all possible sums into an array if the value range is small. The expected tradeoff is between a flexible set-based DP and a denser offset-array DP when the sum range is bounded.

What if the total sum is huge but the array length is small?

The standard DP may become too expensive because its cost depends on target. For small n, a meet-in-the-middle approach is more appropriate. Split the array into two halves, enumerate all subset sums for each half, then check whether a sum from the left half can pair with a sum from the right half to reach the target.

This changes the cost to about O(2^(n/2)) space and time, plus sorting or hash lookup. It is much better when n is small and values are large, but worse than the DP when the target sum is modest.