Partition Equal Subset Sum

Step 1: Reduce to "is there a subset with sum target?"

If the total is odd, the answer is false. Otherwise one subset must sum to target = total / 2, and the rest automatically sums to the other half.

Step 2: Brute force: include or exclude each number

Each number is either in the subset or not. A recursive search tries both, which is O(2ⁿ):

Step 3: Track which sums are reachable

Only the sums matter, and they are at most target. Keep reachable[s]: can some subset of the numbers seen so far sum to s? Start with only 0 reachable. Each new number v makes s reachable if s - v already was:

Step 4: Loop the sums downward

Updating from high sums to low means reachable[s - v] still holds the value from before v was added, so each number is used at most once. Going upward would let v be added again and again.

nums = [1, 5, 11, 5], total 22, target 11.

11 is reachable, so the answer is true.

A boolean array of size target + 1 replaces the set of sums.

public class PartitionEqualSubset {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int v : nums) {
            total += v;
        }
        if (total % 2 != 0) {
            return false; // an odd total cannot split into two equal halves
        }
        int target = total / 2;
        boolean[] reachable = new boolean[target + 1]; // reachable[s]: some subset sums to s
        reachable[0] = true;
        for (int v : nums) {
            for (int s = target; s >= v; s--) { // go down so each number is used once
                reachable[s] = reachable[s] || reachable[s - v];
            }
        }
        return reachable[target];
    }
}

The original implementation, PartitionEqualSubsetSum.java, is on GitHub.

• Time: O(n × target).
• Space: O(target).

Counting the subsets instead of checking for one gives Target Sum.