☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Partition equal subset sum

Hard TUF ID 321 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an array nums of positive integers, decide whether it can be split into two groups such that every element goes into exactly one group and both groups have the same sum. Return true or false.

This is LeetCode 416. Constraints: 1 ≤ n ≤ 200 and 1 ≤ nums[i] ≤ 100, so the total is at most 20,000 and fits easily in an int.

Example 1

nums = [1, 5, 11, 5]
answer = true        // {1, 5, 5} and {11} both sum to 11

Example 2

nums = [1, 2, 3, 5]
answer = false       // the total is 11, which is odd, so two equal halves are impossible

Example 3

nums = [1, 2, 5]
answer = false       // the total 8 is even, but no subset sums to 4

Reducing to subset sum

Let the total be S. If the two groups have equal sums, each must sum to S / 2. Two facts follow immediately:

  1. If S is odd, the answer is false. No further work is needed.
  2. If S is even, the question becomes: is there a subset with sum exactly S / 2? If there is, the elements not in it automatically sum to S - S / 2 = S / 2, so the complement is the other group.

So this problem is the subset-sum problem with the target fixed at half the total. All four approaches below compute the total first, return false for an odd total, and then answer the subset-sum question for half = S / 2.

The reduction is the real insight. Trying to build both groups at once, tracking two running sums, would double the state for no gain: once one group is fixed, the other is determined.

Approach 1: Recursion

Intuition. Let f(i, t) mean: can some subset of nums[0..i] sum to exactly t? Each element is either skipped or taken (taken only if it fits in the remaining t). The recursion stops when nothing is missing (t == 0, the empty subset works) or when a single element is left (i == 0, the answer is whether that element equals t).

f(i, 0) = true
f(0, t) = (nums[0] == t)
f(i, t) = f(i - 1, t)  OR  (nums[i] ≤ t AND f(i - 1, t - nums[i]))
answer  = S is even AND f(n - 1, S / 2)

Algorithm.

  1. Compute S. If it is odd, return false.
  2. Return canReach(n - 1, S / 2) using the recurrence above.
static boolean recursive(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;              // an odd total cannot be split into two equal integers
    return canReach(nums.length - 1, total / 2, nums);
}

static boolean canReach(int i, int t, int[] nums) {
    if (t == 0) return true;
    if (i == 0) return nums[0] == t;
    boolean notTake = canReach(i - 1, t, nums);
    boolean take = nums[i] <= t && canReach(i - 1, t - nums[i], nums);
    return notTake || take;
}

Complexity. Time O(2^n): two branches per element. Space O(n) recursion depth.

Approach 2: Memoization

Intuition. The state (i, t) has n choices for i and S / 2 + 1 choices for t, at most 200 × 10,001 here. The recursion tree, by contrast, has up to 2^200 nodes, because many different choices among the later elements leave the same remainder. Store each state’s answer the first time it is computed.

Algorithm.

  1. Compute S; return false if it is odd.
  2. Allocate dp[n][half + 1] filled with -1 (0 and 1 mean false and true).
  3. Run the recursion, consulting and filling the table.
static boolean memoization(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int half = total / 2;
    int[][] dp = new int[nums.length][half + 1];   // -1 = unknown, 0 = false, 1 = true
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(nums.length - 1, half, nums, dp);
}

static boolean memo(int i, int t, int[] nums, int[][] dp) {
    if (t == 0) return true;
    if (i == 0) return nums[0] == t;
    if (dp[i][t] != -1) return dp[i][t] == 1;
    boolean res = memo(i - 1, t, nums, dp) || (nums[i] <= t && memo(i - 1, t - nums[i], nums, dp));
    dp[i][t] = res ? 1 : 0;
    return res;
}

Complexity. Time O(n · S): each of the n · (S / 2 + 1) states is solved once. Space O(n · S) plus O(n) stack.

Approach 3: Tabulation

Intuition. Fill dp[i][t] row by row. Row 0 knows only two reachable sums, 0 and nums[0]. Every later row copies the reachable sums of the previous row (skip nums[i]) and adds those that are nums[i] more than a previously reachable sum (take nums[i]).

The guard nums[0] ≤ half matters: in [100, 1, 1, 1, 1] the half is 52, and dp[0][100] would be out of bounds.

Algorithm.

  1. Compute S; return false if it is odd. Let half = S / 2.
  2. Set dp[i][0] = true for every i, and dp[0][nums[0]] = true if it fits.
  3. For i ≥ 1 and 1 ≤ t ≤ half: dp[i][t] = dp[i - 1][t] || (nums[i] ≤ t && dp[i - 1][t - nums[i]]).
  4. Return dp[n - 1][half].
static boolean tabulation(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int n = nums.length, half = total / 2;
    boolean[][] dp = new boolean[n][half + 1];
    for (int i = 0; i < n; i++) dp[i][0] = true;
    if (nums[0] <= half) dp[0][nums[0]] = true;
    for (int i = 1; i < n; i++) {
        for (int t = 1; t <= half; t++) {
            dp[i][t] = dp[i - 1][t] || (nums[i] <= t && dp[i - 1][t - nums[i]]);
        }
    }
    return dp[n - 1][half];
}

Complexity. Time O(n · S), space O(n · S).

Approach 4: Space optimized, one array

Intuition. Row i reads row i - 1 only, at index t and at the smaller index t - nums[i]. That allows a single array, reach, updated in place, as long as t goes from high to low. When we write reach[t], the cell we read, reach[t - x], has a smaller index and therefore has not been touched yet in this round, so it still describes the previous elements only.

Going from low to high would be wrong. Processing x = 5 with reach = {0, 1} from left to right sets reach[5] from reach[0], and then sets reach[10] from the freshly written reach[5]. That claims 10 = 5 + 5 using a single 5, which is the unbounded-knapsack update, not this one.

A small bonus of this form: once reach[half] becomes true we can stop immediately.

Algorithm.

  1. Compute S; return false if it is odd. Set reach[0] = true.
  2. For each element x, for t from half down to x: if reach[t - x], set reach[t] = true. Return true as soon as reach[half] is set.
  3. Return reach[half].
static boolean spaceOptimized(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int half = total / 2;
    boolean[] reach = new boolean[half + 1];       // reach[t]: some subset of the elements seen so far sums to t
    reach[0] = true;
    for (int x : nums) {
        for (int t = half; t >= x; t--) {          // right to left: reach[t - x] is still the old value
            if (reach[t - x]) reach[t] = true;
        }
        if (reach[half]) return true;              // early exit once the half is reachable
    }
    return reach[half];
}

Dry run on Example 1 (half = 11), listing the reachable sums after each element:

element reachable sums reach[11]?
start {0} no
1 {0, 1} no
5 {0, 1, 5, 6} no
11 {0, 1, 5, 6, 11} yes, return true

The last 5 is never processed: the early exit fires as soon as 11 is reachable. The subset found is {11}, and its complement {1, 5, 5} is the other half.

Complexity. Time O(n · S), space O(S).

Edge cases and pitfalls