110.Partition Equal Subset Sum

Medium1-D Dynamic Programming · 12/12

Problem

Given an array of positive integers nums, decide whether it can be split into two subsets with equal sums. Every element must go into exactly one of the two subsets.

Return true if such a partition exists, otherwise false.

Examples

Input:  nums = [1, 5, 11, 5]
Output: true
Explanation: [1, 5, 5] and [11] both sum to 11.

Input:  nums = [1, 2, 3, 5]
Output: false
Explanation: The total is 11, which is odd — it can't be split evenly.

Input:  nums = [2, 2, 3, 5]
Output: false
Explanation: Total 12, target 6, but no subset sums to 6.

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 100

💡 Key Insight

If the total S is odd, the answer is false. Otherwise the question becomes "is there a subset summing to target = S / 2?" — the other elements automatically sum to S / 2 too. That's 0/1 knapsack: can(i, t) = can(i + 1, t) || can(i + 1, t - nums[i]) (skip or take element i). Since target <= 200 · 100 / 2 = 10,000, the table is small, and iterating t downwards lets one boolean array of size target + 1 do the work of the whole 2-D table.

Recursion (Brute Force)

TimeO(2ⁿ)SpaceO(n)

Intuition

For each element decide: put it in the subset that should reach target, or leave it out. Succeed if the remaining target hits exactly 0.

Recurrence: can(i, t) = true if t == 0; false if i == n or t < 0; otherwise can(i + 1, t) || can(i + 1, t - nums[i]).

Algorithm

sum all elements; if odd, return false.
dfs(i, t) as in the recurrence.
Return dfs(0, sum / 2).

Visualization

nums = [1, 5, 11, 5], target = 11 (partial). The state (2, 5) — "from index 2, still need 5" — is reached twice.

flowchart TD
    A["can(0, 11)"] -->|"take 1"| B["can(1, 10)"]
    A -->|"skip 1"| C["can(1, 11)"]
    B -->|"take 5"| D["can(2, 5)"]
    B -->|"skip 5"| E["can(2, 10)"]
    C -->|"take 5"| F["can(2, 6)"]
    C -->|"skip 5"| G["can(2, 11)"]
    D -->|"skip 11"| H["can(3, 5)"]
    H -->|"take 5"| I["can(4, 0) = true"]
    G -->|"take 11"| J["can(3, 0) = true"]

Code

java

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % 2 != 0) {
            return false; // odd total can't be halved
        }
        return dfs(nums, 0, sum / 2);
    }

    // can some subset of nums[i..] sum to exactly t?
    private boolean dfs(int[] nums, int i, int t) {
        if (t == 0) {
            return true;
        }
        if (i == nums.length || t < 0) {
            return false;
        }
        return dfs(nums, i + 1, t) || dfs(nums, i + 1, t - nums[i]);
    }
}

Complexity

Time: O(2ⁿ) — each element is in or out.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n · target)SpaceO(n · target)

Intuition

The state (i, t) has at most n × (target + 1) values. Cache each one; many different take/skip histories collapse onto the same (i, t).

Algorithm

Odd-sum check, target = sum / 2.
Boolean[][] memo = new Boolean[n][target + 1].
dfs(i, t): base cases as before; otherwise return the cached value or compute, store, return.

Dry Run

nums = [2, 2, 3, 5], target = 6
dfs(0,6) → take 2 → dfs(1,4) → take 2 → dfs(2,2) → 3 too big, skip → dfs(3,2) → 5 too big → false
                              skip 2 → dfs(2,4) → take 3 → dfs(3,1) false; skip → dfs(3,4) false
         → skip 2 → dfs(1,6) → take 2 → dfs(2,4)   cache hit: false
                              skip 2 → dfs(2,6) → take 3 → dfs(3,3) false; skip → dfs(3,6) → take 5 → dfs(4,1) false
→ false

Code

java

class Solution {
    private Boolean[][] memo;

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        memo = new Boolean[nums.length][target + 1];
        return dfs(nums, 0, target);
    }

    private boolean dfs(int[] nums, int i, int t) {
        if (t == 0) {
            return true;
        }
        if (i == nums.length || t < 0) {
            return false;
        }
        if (memo[i][t] != null) {
            return memo[i][t];
        }
        boolean result = dfs(nums, i + 1, t) || dfs(nums, i + 1, t - nums[i]);
        memo[i][t] = result;
        return result;
    }
}

Complexity

Time: O(n · target) — each state computed once.
Space: O(n · target) — memo table, plus O(n) recursion.

Bottom-Up Tabulation

TimeO(n · target).SpaceO(n · target).

Intuition

Let dp[i][t] = "some subset of the first i elements sums to t". Row i is built from row i - 1: either element i - 1 is not used (dp[i-1][t]) or it is (dp[i-1][t - nums[i-1]]).

Recurrence: dp[i][t] = dp[i-1][t] || (t >= nums[i-1] && dp[i-1][t - nums[i-1]]), with dp[i][0] = true.

Algorithm

Odd-sum check; target = sum / 2.
boolean[][] dp = new boolean[n + 1][target + 1]; dp[i][0] = true for all i.
Fill rows i = 1..n, columns t = 1..target.
Return dp[n][target].

Dry Run

nums = [1, 5, 11, 5], target = 11 (T / .; only a few columns shown):

first i items	t=0	1	5	6	10	11
0 (none)	T	.	.	.	.	.
1 {1}	T	T	.	.	.	.
2 {1,5}	T	T	T	T	.	.
3 {1,5,11}	T	T	T	T	.	T
4 {1,5,11,5}	T	T	T	T	T	T

dp[3][11] becomes true by taking 11 on top of dp[2][0].

Code

java

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2, n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true; // empty subset sums to 0
        }
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int t = 1; t <= target; t++) {
                dp[i][t] = dp[i - 1][t];                // skip num
                if (t >= num) {
                    dp[i][t] = dp[i][t] || dp[i - 1][t - num]; // take num
                }
            }
        }
        return dp[n][target];
    }
}

Complexity

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

1-D Space-Optimized DPOptimal

TimeO(n · target)SpaceO(target)

Intuition

Row i only reads row i - 1, so keep a single array dp[t] = "some subset seen so far sums to t". For each number, update t from high to low: then dp[t - num] still holds the previous row's value, so num can't be used twice in the same pass. Stop early once dp[target] is true.

Algorithm

Odd-sum check; target = sum / 2; dp[0] = true.
For each num: for t = target down to num: dp[t] = dp[t] || dp[t - num].
If dp[target] becomes true, return true.
Return dp[target].

Dry Run

flowchart TD
    A["nums=[1,5,11,5], target=11<br/>reachable = {0}"] -->|"num=1"| B["reachable = {0,1}"]
    B -->|"num=5"| C["reachable = {0,1,5,6}"]
    C -->|"num=11"| D["reachable = {0,1,5,6,11}"]
    D --> E{"dp[11]?"}
    E -->|"yes"| F["return true"]

Iterating downward for num = 5: t = 6 reads the old dp[1] = T, t = 5 reads dp[0] = T; t = 10 reads the old dp[5] = F, so 5 is not counted twice.

Code

java

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1]; // dp[t]: some subset sums to t
        dp[0] = true;
        for (int num : nums) {
            // go right-to-left so each num is used at most once
            for (int t = target; t >= num; t--) {
                dp[t] = dp[t] || dp[t - num];
            }
            if (dp[target]) {
                return true; // early exit
            }
        }
        return dp[target];
    }
}

Complexity

Time: O(n · target) — at most 200 × 10,000 = 2·10⁶ updates.
Space: O(target) — one boolean array.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2ⁿ)	O(n)
Top-Down Memoization	O(n · target)	O(n · target)
Bottom-Up Tabulation	O(n · target)	O(n · target)
1-D Space-Optimized DP	O(n · target)	O(target)

Common Pitfalls

Skipping the odd-sum check — then sum / 2 truncates and you search for the wrong target.
Iterating t upwards in the 1-D version: dp[t - num] would already include num, turning it into unbounded knapsack (e.g. [1, 2, 5] would wrongly "reach" 4 = 2 + 2).
Allocating the memo as boolean[][] — false is a valid answer, so there's no "not computed" state; use Boolean[][].
Calling it "split into two subarrays" — the subsets need not be contiguous.