Partition Equal Subset Sum

Given a non-empty array of positive integers, return true if it can be split into two subsets whose sums are equal.

LeetCode: 416. Partition Equal Subset Sum

Example

[1, 6, 11, 6]  ->  true    ([6, 6] and [1, 11], both 12)
[2, 6, 7]      ->  false

Two equal halves each sum to total / 2. So the question becomes: is there a subset that sums to total / 2? If total is odd, the answer is immediately false.

Brute force: include or skip each element

canReach(nums, i, target) decides using only the elements from index i onward.

public class Main {
    static boolean canReach(int[] nums, int i, int target) {
        if (target == 0) return true;
        if (i == nums.length) return false;
        int x = nums[i];
        return (x <= target && canReach(nums, i + 1, target - x)) || canReach(nums, i + 1, target);
    }

    static boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        return total % 2 == 0 && canReach(nums, 0, total / 2);
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 6, 11, 6}) + " " + canPartition(new int[]{2, 6, 7}));
    }
}

true false

Time: O(2ⁿ). Space: O(n) for the recursion.

Optimal: which sums are reachable

Keep reachable[s]: can some subset of the elements seen so far sum to s? Start with only reachable[0] = true (the empty subset). Each element x either stays out, or is added to a subset that already reached s - x:

reachable[s] = reachable[s] || reachable[s - x]

Loop over s downwards, from target to x. Then reachable[s - x] still holds the value from before x was considered, so x is used at most once. (Looping upwards would let x be reused, which is the unlimited version used in Coin Change.)

public class Main {
    static boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 == 1) return false;
        int target = total / 2;
        boolean[] reachable = new boolean[target + 1];
        reachable[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                reachable[s] |= reachable[s - x];
            }
        }
        return reachable[target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 6, 11, 6}) + " " + canPartition(new int[]{2, 6, 7}));
        System.out.println(canPartition(new int[]{1, 5, 11, 5}) + " " + canPartition(new int[]{1, 2, 3, 5}));
    }
}

true false
true false

Time: O(n · total). Space: O(total).

This is the 0/1 knapsack pattern: each item is used at most once, and the table is indexed by capacity. The running time depends on the size of the numbers, not only on how many there are, so it's practical when the sum is moderate (LeetCode limits it to 20,000).

Edge cases

• Odd total: false without any DP.
• Single element: false, because the other subset would be empty and sum to 0.
• An element larger than total / 2: can't be in either half together with anything; the inner loop doesn't run for it.
• Large sums: total is an int, so a sum above Integer.MAX_VALUE wraps silently. The table also needs total / 2 + 1 booleans, which limits the practical input size.