Equal Subset Sum Partition Problem

Can an array of positive integers be split into two subsets with equal sums? The problem looks like a search over 2ⁿ partitions and reduces, in one step, to a question about a single subset, after which it is the 0/1 knapsack with a different objective.

Written against Java 17.

The problem

[1, 5, 11, 5]     -> true      {1, 5, 5} and {11}, both summing to 11
[1, 2, 3, 5]      -> false     total 11 is odd
[1, 2, 5]         -> false     total 8 is even, but no subset sums to 4

The second example shows the cheap rejection that handles half of all inputs; the third shows why it is not sufficient on its own.

Two reductions before any algorithm

An odd total is immediately false. Two equal integer subsets sum to an even number, so a total that is odd cannot be split. One line, and it eliminates roughly half of all inputs.

Finding one subset is enough. If a subset sums to total / 2, everything not in it sums to the same amount by arithmetic. There is no need to construct the second subset or to consider partitions as pairs.

So the question becomes: is there a subset summing to total / 2? That is subset-sum, a well-studied problem, and the 2ⁿ search is gone.

static boolean canPartition(int[] nums) {
    int total = Arrays.stream(nums).sum();
    if (total % 2 != 0) return false;
    return subsetSumExists(nums, total / 2);
}

The two-dimensional table

static boolean subsetSumExists(int[] nums, int target) {
    boolean[][] reachable = new boolean[nums.length + 1][target + 1];

    for (int i = 0; i <= nums.length; i++) {
        reachable[i][0] = true;                  // sum 0 is always reachable — take nothing
    }

    for (int i = 1; i <= nums.length; i++) {
        for (int sum = 1; sum <= target; sum++) {
            reachable[i][sum] = reachable[i - 1][sum];                  // skip item i

            if (nums[i - 1] <= sum) {
                reachable[i][sum] |= reachable[i - 1][sum - nums[i - 1]];   // take item i
            }
        }
    }
    return reachable[nums.length][target];
}

reachable[i][sum] answers “using the first i items, can I reach exactly sum?”. Each cell is the OR of two decisions: leave the item out, or take it and ask whether the remainder was reachable without it.

The base case reachable[i][0] = true is the empty subset. Forgetting it makes every cell false, because nothing ever bottoms out.

nums[i - 1] rather than nums[i], because the table is 1-indexed by item count and the array is 0-indexed. That off-by-one is where most implementations of this go wrong.

Collapsing to one dimension

Row i depends only on row i - 1, so one array suffices:

static boolean subsetSumExists(int[] nums, int target) {
    boolean[] reachable = new boolean[target + 1];
    reachable[0] = true;

    for (int num : nums) {
        for (int sum = target; sum >= num; sum--) {     // BACKWARDS
            reachable[sum] |= reachable[sum - num];
        }
    }
    return reachable[target];
}

O(n · target) time, O(target) space.

The inner loop must run backwards, and this is the single most important line in the problem.

Going forwards, reachable[sum - num] may already have been updated by the current item in this same pass. The item would then be counted twice, and the algorithm answers a different question, the unbounded knapsack, where each item may be reused.

Concretely, with nums = [3] and target = 6: forwards, reachable[3] becomes true, then reachable[6] |= reachable[3] also becomes true, claiming that a single 3 sums to 6. Backwards, reachable[6] is computed from reachable[3] while that is still false from the previous item’s row, and the answer is correct.

Backwards means every value read on the right is from the previous row. That is the whole reason for the direction, and it is worth stating in a comment because it looks arbitrary.

Early exits worth adding

static boolean canPartition(int[] nums) {
    int total = 0, max = 0;
    for (int n : nums) {
        total += n;
        max = Math.max(max, n);
    }

    if (total % 2 != 0) return false;
    int target = total / 2;
    if (max > target) return false;      // one element exceeds half the total

    boolean[] reachable = new boolean[target + 1];
    reachable[0] = true;

    for (int num : nums) {
        for (int sum = target; sum >= num; sum--) {
            reachable[sum] |= reachable[sum - num];
        }
        if (reachable[target]) return true;      // stop as soon as it is reachable
    }
    return reachable[target];
}

The max > target check catches [1, 1, 100] without building a table, and the in-loop check often returns after a fraction of the items.

Neither changes the worst case. Both matter in practice, and the second is free, the check is a single array read once per item.

What “pseudo-polynomial” means

O(n · target) looks polynomial and is not, in the formal sense. target is a value, not an input size, and a number is written in binary, so a target of one million is six or seven characters of input and a million columns of table.

Doubling the number of digits squares the running time. That is why subset-sum is NP-complete despite this apparently efficient solution: the algorithm is polynomial in the magnitude of the numbers, not in the length of the input.

The practical consequence is a memory limit rather than a time limit. Values up to 100 with 200 items gives a target of 10,000 and a trivial table. Values up to 10⁹ makes the array impossible to allocate, and no amount of optimisation helps, a different approach, such as meet-in-the-middle at O(2^(n/2)), is needed.

Recovering the actual subsets

The boolean answer rarely satisfies a caller. Recovering the partition needs the 2-D table, walked backwards from the final cell:

static List<Integer> findSubset(int[] nums, int target, boolean[][] reachable) {
    List<Integer> chosen = new ArrayList<>();
    int sum = target;

    for (int i = nums.length; i > 0 && sum > 0; i--) {
        if (!reachable[i - 1][sum]) {          // this item was necessary
            chosen.add(nums[i - 1]);
            sum -= nums[i - 1];
        }
    }
    return chosen;
}

!reachable[i - 1][sum] means the sum was not achievable without item i, so it must be in the subset. Where both are true, either choice works and taking the skip keeps the subset smaller.

This is the reason to keep the 2-D table when the subsets are wanted: the collapsed version overwrites the history the walk-back needs.

Related shapes

The same table answers a family of questions with a changed objective:

• Minimum subset-sum difference: instead of testing reachable[target], scan downwards from total / 2 for the largest reachable sum. The difference is total - 2 * thatSum.
• Count of subsets with a given sum: replace the boolean with an int count and |= with +=.
• Target sum with plus and minus signs: Assigning signs to reach S is the same as choosing a subset summing to (total + S) / 2.

Recognising the reduction is worth more than the code. Each of those looks like a different problem and is this one with two lines changed.

More in the algorithms guides.

Frequently asked questions

What is the first check?

Whether the total is odd. Two equal integer subsets sum to an even number, so an odd total is immediately false.

Why is finding one subset enough?

Everything not in it sums to the same amount by arithmetic. The second subset never has to be constructed.

Why must the inner loop run backwards?

Going forwards, a cell updated by the current item is read again in the same pass, so the item is counted twice. That solves the unbounded knapsack instead.

What is the time complexity?

O(n · total/2), and O(total/2) space with the one-dimensional table.

Why is that not truly polynomial?

The target is a value, not an input length. Numbers are written in binary, so doubling the digits squares the running time. That is what “pseudo-polynomial” means.

When does this approach stop working?

When the values are large enough that the table cannot be allocated, around 10⁹. Meet-in-the-middle at O(2^(n/2)) is the alternative.

What early exits are worth adding?

Reject when any single element exceeds half the total, and return as soon as the target becomes reachable during the item loop.

Why nums[i - 1] in the 2-D version?

The table is indexed by item count starting at 0 while the array is indexed from 0. That off-by-one is the usual bug.

How do I recover the actual subsets?

Keep the 2-D table and walk back from the final cell: an item was necessary wherever the sum was not reachable without it.

Does this work with negative numbers or zeros?

Zeros are harmless. Negatives break it, the target is no longer a bound and the array index can go out of range. Shift the range or use a map.