#416 Partition Equal Subset Sum

Mediumsolve on LeetCode ↗

frequently reported atAmazon Google Microsoft Meta

the problem

In plain words

Can nums be split into two subsets with equal sums?

in nums = [1,5,11,5]

out true

[1,5,5] and [11].

in nums = [1,2,3,5]

out false

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

pattern0/1 knapsack

Two equal halves means one subset sums to exactly total / 2. That's 0/1 knapsack with booleans: can I make sum s using each number at most once?

solutions

From brute force to optimal

canMake(i, target) = canMake(i+1, target − nums[i]) || canMake(i+1, target).

Odd total → false.
target = 0 → true; out of numbers → false.

timeO(2ⁿ)

Every number is taken or skipped.

spaceO(n)

Recursion depth.

javajava.util.*

1class Solution {2    public boolean canPartition(int[] nums) {3        int total = Arrays.stream(nums).sum();4        if (total % 2 != 0) return false; // odd total can never split evenly5        return canMake(nums, 0, total / 2);6    }7 8    /** Can some subset of nums[i..] add up to exactly target? */9    private boolean canMake(int[] nums, int i, int target) {10        if (target == 0) return true;11        if (i == nums.length || target < 0) return false;12        return canMake(nums, i + 1, target - nums[i]) // take nums[i]13            || canMake(nums, i + 1, target);          // skip nums[i]14    }15}

States are (i, target): n × (S + 1), where S = total / 2.

Boolean[][] memo, null = unknown.

timeO(n·S)

Each state once.

spaceO(n·S)

The memo.

javajava.util.*

1class Solution {2    public boolean canPartition(int[] nums) {3        int total = Arrays.stream(nums).sum();4        if (total % 2 != 0) return false;5        Boolean[][] memo = new Boolean[nums.length][total / 2 + 1]; // null = unknown6        return canMake(nums, 0, total / 2, memo);7    }8 9    private boolean canMake(int[] nums, int i, int target, Boolean[][] memo) {10        if (target == 0) return true;11        if (i == nums.length || target < 0) return false;12        if (memo[i][target] != null) return memo[i][target];13        return memo[i][target] = canMake(nums, i + 1, target - nums[i], memo) || canMake(nums, i + 1, target, memo);14    }15}

dp[i][s] = can the first i numbers make s?

dp[i][0] = true.
dp[i][s] = dp[i−1][s] || dp[i−1][s − nums[i−1]].

timeO(n·S)

One step per cell.

spaceO(n·S)

The table.

javajava.util.*

1class Solution {2    public boolean canPartition(int[] nums) {3        int total = Arrays.stream(nums).sum();4        if (total % 2 != 0) return false;5        int half = total / 2, n = nums.length;6        boolean[][] dp = new boolean[n + 1][half + 1]; // dp[i][s]: can the first i numbers make s?7        for (int i = 0; i <= n; i++) dp[i][0] = true;  // the empty subset makes 08        for (int i = 1; i <= n; i++) {9            for (int s = 1; s <= half; s++) {10                dp[i][s] = dp[i - 1][s];                                  // skip nums[i-1]11                if (nums[i - 1] <= s) dp[i][s] |= dp[i - 1][s - nums[i - 1]]; // take it12            }13        }14        return dp[n][half];15    }16}

sim

Same shape: the 0/1 knapsack table

loading simulation…

javajava.util.*

1class Knapsack01 {2    /** dp[i][c] = best value using only the first i items with capacity c. */3    static int knapsack(int[] wt, int[] val, int cap) {4        int n = wt.length;5        int[][] dp = new int[n + 1][cap + 1]; // row 0 = no items = value 06        for (int i = 1; i <= n; i++) {7            for (int c = 0; c <= cap; c++) {8                dp[i][c] = dp[i - 1][c]; // option 1: skip item i9                if (wt[i - 1] <= c) {10                    // option 2: take item i once, so look at the row ABOVE11                    dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - wt[i - 1]] + val[i - 1]);12                }13            }14        }15        return dp[n][cap];16    }17}

Rolling row; go downward so each number is used at most once.

dp[0] = true.
for x: for s = S down to x: dp[s] |= dp[s − x].
Early exit when dp[S] is true.

timeO(n·S)

n numbers × up to S sums (≤ 200 × 10⁴ = 2·10⁶).

spaceO(S)

One row.

javajava.util.*

1class Solution {2    public boolean canPartition(int[] nums) {3        int total = Arrays.stream(nums).sum();4        if (total % 2 != 0) return false;5        int half = total / 2;6        boolean[] dp = new boolean[half + 1]; // dp[s]: can some numbers seen so far make s?7        dp[0] = true; // the empty subset makes 08        for (int x : nums) {9            for (int s = half; s >= x; s--) { // DOWNWARD: each number used at most once10                dp[s] = dp[s] || dp[s - x]; // keep s, or reach it by adding x to s - x11            }12            if (dp[half]) return true; // early exit13        }14        return dp[half];15    }16}

sim

One row, swept downward

loading simulation…

javajava.util.*

1class Solution {2    public boolean canPartition(int[] nums) {3        int total = Arrays.stream(nums).sum();4        if (total % 2 != 0) return false;5        int half = total / 2;6        boolean[] dp = new boolean[half + 1]; // dp[s]: can some numbers seen so far make s?7        dp[0] = true; // the empty subset makes 08        for (int x : nums) {9            for (int s = half; s >= x; s--) { // DOWNWARD: each number used at most once10                dp[s] = dp[s] || dp[s - x]; // keep s, or reach it by adding x to s - x11            }12            if (dp[half]) return true; // early exit13        }14        return dp[half];15    }16}

in the room

How to say it in the interview

talk track

"Equal halves ⇔ subset with sum total/2" — say this reduction first; then it's textbook 0/1 knapsack.

traps

Forgetting the odd-total early exit.
Upward inner loop reuses the same number twice → false positives.

what they ask next

Follow-ups

Target Sum (LC 494)?

Count subsets with sum (total + target) / 2 — same table with + instead of ||.

Last Stone Weight II (LC 1049)?

Find the reachable subset sum closest to total / 2.

before you submit

Edge cases to test

Odd total → false at once.
One number → false (the other half would be empty).
[3,4,5] → false: 6 = 3 + 3 only if the 3 is reused — exactly the bug an upward loop has.

practise next