Partition Equal Subset Sum – Solution & Complexity

Q: What is the time and space complexity of Partition Equal Subset Sum?

The optimal Partition Equal Subset Sum solution runs in `O(n * sum)` time and `O(sum)` space. Reduce to a subset-sum for half the total, then fill a 1D boolean reachability table iterating each value from high sums down to avoid reusing it twice.

Q: What is the most efficient way to solve Partition Equal Subset Sum?

Reduce to a subset-sum for half the total, then fill a 1D boolean reachability table iterating each value from high sums down to avoid reusing it twice. This gives `O(n * sum)` time complexity, and is a classic dynamic programming and arrays problem.

Q: How do you solve Partition Equal Subset Sum in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Partition Equal Subset Sum solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Partition Equal Subset Sum an easy or hard interview question?

Partition Equal Subset Sum is generally rated **Medium**. It tests dynamic programming and arrays, which are common coding-interview patterns.

Solution Walkthrough

1. Reduce to subset sum

Splitting into two equal halves means finding a subset that sums to exactly total / 2.
If total is odd, no such subset exists, so return false immediately.
Otherwise the question becomes: can any subset reach target = total / 2?

2. Fill a 2D reachability table

Let dp[i][s] be true when some subset of the first i values sums to s.
A sum of 0 is always reachable with the empty subset.
Each value is either skipped (dp[i-1][s]) or taken (dp[i-1][s - nums[i-1]]).

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True
    for i in range(1, n + 1):
        for s in range(1, target + 1):
            dp[i][s] = dp[i - 1][s]
            if s >= nums[i - 1] and dp[i - 1][s - nums[i - 1]]:
                dp[i][s] = True
    return dp[n][target]

3. Compress to one boolean row

Each row only reads the row directly above, so a single boolean array of size target + 1 suffices.
Iterate the inner sum from high down to value; going downward guarantees each number is used at most once (a 0/1 knapsack, not unbounded).

4. Optimal 1D solution

Start with dp[0] = true.
For every value, mark dp[sum] reachable whenever dp[sum - value] was already reachable, scanning sums downward.
The answer is dp[target].

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for value in nums:
        for s in range(target, value - 1, -1):
            if dp[s - value]:
                dp[s] = True
    return dp[target]

5. Dry run

Trace nums = [1,5,11,5], target = 11.

Start: reachable sums {0}.
After 1: {0,1}.
After 5: {0,1,5,6}.
After 11: {0,1,5,6,11,...} — 11 is now reachable, so the answer is true.

6. Common mistakes and follow-ups

Iterating the inner sum upward, which reuses the same element multiple times and turns it into unbounded knapsack.
Forgetting the odd-total shortcut, or comparing against total instead of total / 2.
Allocating dp of size target instead of target + 1 and missing the exact-target cell.
Follow-up: how would you recover the actual subset, not just whether one exists?

7. Edge cases to test mentally

A single element can never be split, so the answer is false.
An odd total is always false.
Two equal elements are always true.

8. Final full solution and complexity

Target half the total and fill a 1D subset-sum table, scanning sums downward per value. Time is O(n * sum) and extra space is O(sum).

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for value in nums:
        for s in range(target, value - 1, -1):
            if dp[s - value]:
                dp[s] = True
    return dp[target]

Partition Equal Subset Sum – Solution & Complexity

Solution Walkthrough

1. Reduce to subset sum

2. Fill a 2D reachability table

3. Compress to one boolean row

4. Optimal 1D solution

5. Dry run

6. Common mistakes and follow-ups

7. Edge cases to test mentally

8. Final full solution and complexity

FAQ

What is the time and space complexity of Partition Equal Subset Sum?

What is the most efficient way to solve Partition Equal Subset Sum?

How do you solve Partition Equal Subset Sum in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Partition Equal Subset Sum an easy or hard interview question?

See also