Advertisement
Home Data Structure Arrays Partition Array into Two Equal Sum Subsets

Partition Array into Two Equal Sum Subsets

0
Advertisement

Title: Partition Array into Two Equal Sum Subsets

In this guide, you will learn how to check whether a Java array of positive integers can be split into two subsets with equal sums. This is the classic Partition Equal Subset Sum problem, and interviewers like it because it turns a subset search into a clean dynamic programming table. You will see the full approach, a working program, a step-by-step trace, and the edge cases a candidate is expected to raise.

Understanding the Problem

Given an array nums of positive integers, decide if it can be divided into two subsets, subsetA and subsetB, so that the sum of elements in subsetA equals the sum of elements in subsetB. Every element of nums must belong to exactly one of the two subsets, and together the subsets must use every element exactly once.

This is not the same as asking for two subsets of equal size. A valid split can have three elements on one side and seven on the other, as long as both sides add up to the same total. The only requirement is that the two sums match.

Approach

The total sum of the array decides everything. If the total is odd, no equal split can exist, since two equal integers can never add up to an odd number. If the total is even, the question becomes simpler: can some subset of nums sum to exactly half the total? That question is answered with a 0/1 knapsack style dynamic programming table.

  1. Compute totalSum, the sum of every element in nums.
  2. If totalSum is odd, return false immediately since an equal split is impossible.
  3. Set target to totalSum / 2, the sum one subset must reach.
  4. Create a boolean array dp of size target + 1, where dp[s] means some subset of the elements processed so far sums to s.
  5. Set dp[0] to true, since an empty subset always sums to 0.
  6. For each number num in nums, scan the dp array from target down to num, setting dp[sum] to true whenever dp[sum - num] is already true.
  7. After every element has been processed, dp[target] is the final answer: true means the array can be partitioned into two equal-sum subsets.

Java Program

Java
import java.util.Arrays;

public class PartitionEqualSumSubsets {

    public static boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (totalSum % 2 != 0) {
            return false;
        }

        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int sum = target; sum >= num; sum--) {
                if (dp[sum - num]) {
                    dp[sum] = true;
                }
            }
        }

        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println("Input array: " + Arrays.toString(nums));

        if (canPartition(nums)) {
            System.out.println("The array can be partitioned into two equal sum subsets.");
        } else {
            System.out.println("The array cannot be partitioned into two equal sum subsets.");
        }
    }
}

Explanation of the Program

The canPartition method starts by adding up every element of nums into totalSum using a single for loop. This total decides whether an equal split is even arithmetically possible.

If totalSum is odd, the method returns false right away. There is no point building the dp table for an array that can never be split evenly.

The target is totalSum / 2, and dp is a boolean array sized target + 1. dp[0] starts as true because a sum of zero is always reachable by choosing no elements.

The outer loop visits each number in nums once. The inner loop walks sum from target down to num, and sets dp[sum] to true when dp[sum - num] is already true, meaning num can extend an existing reachable sum into a new one.

Scanning the inner loop backward, from target down to num, is what keeps each element usable only once per pass. Scanning forward would let the same element be added to a sum more than once, turning 0/1 knapsack into unbounded knapsack.

Once every number has been processed, dp[target] holds the answer. If it is true, some subset of nums sums to target, which means the remaining elements sum to the other half as well.

Step-by-Step Trace

For nums = [3, 1, 4, 2, 2, 6], the total sum is 18 and target is 9. Here is how dp[9] evolves as each element is processed.

Iterationnumdp[9] beforeNew sums addeddp[9] after
13no3no
21no1, 4no
34no5, 7, 8no
42no2, 6, 9yes
52yesnone (no-op)yes
66yesnone (no-op)yes

At the end of iteration i, dp[s] is true for every sum s that some subset of the first i elements of nums can produce, which is why dp[9] flips to true as soon as enough elements combine to reach the target, here on iteration 4.

Examples

Example 1: A Simple Equal Split

An array where two numbers on each side add up to the same total.

Java
int[] nums = {1, 2, 3, 4};
System.out.println(canPartition(nums));
// Output: true

Example 2: Even Total That Still Fails

A useful reminder that an even total sum is necessary but not sufficient. The elements still have to combine into the right sum.

Java
int[] nums = {2, 2, 3, 5};
System.out.println(canPartition(nums));
// Output: false

Example 3: Odd Total Sum

The fastest rejection case. canPartition never has to touch the dp table because the total itself rules out an equal split.

Java
int[] nums = {1, 2, 3, 9};
System.out.println(canPartition(nums));
// Output: false

Common Mistakes to Avoid

These are the slips that most often turn a correct idea into a wrong answer or a crash on this problem.

  • Skipping the total-sum parity check – jumping straight into building the dp table without checking totalSum % 2 != 0 first lets integer division silently truncate the target for an odd total. Check parity before computing target.
  • Scanning the dp array forward – updating dp[sum] for sum from num up to target lets a single element be reused multiple times in the same pass, reporting true for sums that actually need two copies of the same value. Always scan from target down to num.
  • Sizing dp as target instead of target + 1 – allocating new boolean[target] throws ArrayIndexOutOfBoundsException the first time the loop writes to dp[target]. Size the array target + 1 so index target is a valid slot.
  • Returning dp[totalSum] instead of dp[target] – checking the wrong index after halving the sum either throws an exception or always reads an unset, default-false cell, making every input report false. Return dp[target], the halved value, not the original total.

Edge Cases to Test

Walk through these input shapes before calling the problem solved.

  • Empty array
  • Single-element array
  • Array with an odd total sum
  • All elements identical
  • Array containing one or more zeros
  • Exactly two elements
  • Very large array with a large target sum
  • Total sum near Integer.MAX_VALUE

Additional Considerations

The algorithm runs in O(n * target) time, where n is the number of elements and target is half the total sum, since the outer loop runs n times and the inner loop runs up to target times. Space usage is O(target) for the dp array, which is a significant improvement over a 2D dp table sized n * target.

A zero in the array never changes the achievable sums, since dp[s] = dp[s - 0] is always true when dp[s] already is, so it is harmless but still worth testing to confirm the loop does nothing unexpected. Large arrays with large values can overflow a 32-bit totalSum before the parity check even runs, which is why production code should accumulate the sum in a long whenever the input range is not already constrained.

If target is very large relative to available memory, a boolean array may be wasteful for sparse inputs. A HashSet<Integer> of reachable sums trades lookup speed for lower memory on arrays where most sums between 0 and target are unreachable.

Interview Follow-up Questions

Once the base solution is working, expect an interviewer to push on these variations.

  • What if negative numbers are allowed in the array? – swap the boolean dp array for a HashSet<Integer> of achievable sums, since sums can now go negative and the target range is no longer anchored at zero.
  • What if you need k equal-sum subsets instead of two? – use backtracking with pruning, trying to fill k buckets of size totalSum / k each, which is a much harder search rather than a single dp pass.
  • What if an exact equal split is impossible and you want the closest possible split? – keep the same dp array and scan backward from target to find the largest reachable sum, since that sum and its complement give the minimum possible difference.
  • What if nums arrives as a read-only stream that does not fit in memory? – exact subset-sum partitioning needs random access to every element, so a single streaming pass cannot solve it exactly. You would need to batch the data or fall back to an approximate bound.

Conclusion

Partitioning an array into two equal-sum subsets comes down to one clean idea: rule out odd totals immediately, then search for a subset that reaches half the sum using a 0/1 knapsack dp table. Once you can trace how dp[target] fills in as each element is processed, the rest of the problem, including the interview variations, follows naturally.

Try adapting the canPartition method to return the actual subsets instead of just a boolean, or to handle the k-subset variation from the follow-up questions above. You can learn more about array-based interview problems like this one in the Arrays category.