Partition Equal Subset Sum — Solution

Problem

Given an array of positive integers, determine whether you can split it into two non-empty groups such that both groups have the same sum. Every element must go to exactly one group.

Example:

• Input: nums = [1, 5, 11, 5]
• Output: true
• Explanation: {11} and {1, 5, 5} each sum to 11.

Counter-example: nums = [1, 2, 3, 5] has total sum 11, which is odd — no equal split is possible, so the answer is false.

Intuition

If two groups have equal sums, each must add up to exactly half the array's total — so the first thing to check is whether that total is even. From there, the problem becomes: is there any subset that hits exactly total / 2? This is the 0/1 knapsack pattern: each element is either included or skipped, and we track every reachable sum as we consider elements one by one.

Approach 1 — 2D DP Table

Build a table where dp[i][j] is true if we can reach sum j using only the first i elements. For each new element, either skip it (copy the row above) or include it (look back by that element's value).

Steps:

1. Compute target = total // 2; return False immediately if total is odd.
2. Create a (n+1) × (target+1) table initialized to False; set dp[i][0] = True for all i (empty subset always reaches sum 0).
3. For each element index i (1-based) and each candidate sum j:
   • Carry forward dp[i-1][j] (skip this element).
   • If nums[i-1] <= j, also OR in dp[i-1][j - nums[i-1]] (include this element).
4. Return dp[n][target].

1def canPartition(nums: list) -> bool:
2    total = sum(nums)
3    if total % 2 != 0:
4        return False
5    target = total // 2
6    n = len(nums)
7    dp = [[False] * (target + 1) for _ in range(n + 1)]
8    for i in range(n + 1):
9        dp[i][0] = True  # empty subset always reaches sum 0
10    for i in range(1, n + 1):
11        for j in range(1, target + 1):
12            dp[i][j] = dp[i - 1][j]  # skip current element
13            if nums[i - 1] <= j:
14                dp[i][j] |= dp[i - 1][j - nums[i - 1]]  # include current element
15    return dp[n][target]

Time: O(n × target) — fill an n × target table once.
Space: O(n × target) — the full 2D boolean table.

Approach 2 — 1D DP (Space-Optimized)

Each row of the 2D table only depends on the row above, so we can collapse to a single array dp[j] meaning "can we reach sum j with the elements seen so far?" The key is iterating j from high to low so each element is used at most once.

Steps:

1. Compute target = total // 2; return False if total is odd.
2. Initialize dp[0..target] to False, with dp[0] = True.
3. For each num in nums, iterate j from target down to num:
   • dp[j] |= dp[j - num]
4. Return dp[target].

1def canPartition(nums: list) -> bool:
2    total = sum(nums)
3    if total % 2 != 0:
4        return False
5    target = total // 2
6    dp = [False] * (target + 1)
7    dp[0] = True  # zero sum is always reachable
8    for num in nums:
9        for j in range(target, num - 1, -1):  # high-to-low prevents reusing the same element
10            dp[j] |= dp[j - num]
11    return dp[target]

Time: O(n × target) — same traversal, one row.
Space: O(target) — single 1D boolean array instead of the full table.

Complexity Summary

Common Mistakes

• Skipping the parity check: If total is odd, no equal split exists. Without this guard you'll silently get a wrong answer or an out-of-bounds error.
• Iterating forward in the 1D DP: Looping j from num up to target instead of downward lets the same element be used multiple times, incorrectly converting this into an unbounded knapsack.
• Not short-circuiting when an element equals the target: If any single element equals target, you can return True immediately — that element alone forms one half.
• Off-by-one in the inner loop bounds: The reverse loop must reach j == num (Python: range(target, num - 1, -1)) so that dp[num - num] = dp[0] = True propagates into dp[num].
• Integer overflow when summing: In languages with fixed-width integers, summing a large array before the parity check can overflow. Compute the total in a wider type or check element bounds first.

Related Problems

• target-sum — assign + or − to each element to reach a target; reduces to a subset sum problem with the same DP structure
• coin-change — find minimum coins to reach a target; the unbounded-knapsack sibling where elements can repeat
• subsets-ii — enumerate all subsets with duplicates; explores the same include/skip decision tree the DP models implicitly
• word-break — can a string be segmented using dictionary words; another boolean reachability DP with a near-identical structure
• unique-paths — count grid paths; a DP table that shares the same 2D → 1D compression technique shown in Approach 2