TL;DR
Reduce to subset-sum for target = total/2, solved with a 1-D boolean DP — O(n·target) time, O(target) space.
Approach 1 — Brute-force recursion
Try every element in-or-out; ask whether any subset hits target = total/2.
Recurrence: can(i, t) = can(i+1, t) OR can(i+1, t - nums[i]). Base: t == 0 → True; i == n or t < 0 → (t == 0).
Each element forks into two branches — take it or skip it — so the call structure is a binary tree. For nums = [1,2,3], target = 3:
flowchart TD
A["can(0, 3)"] -->|take 1| B["can(1, 2)"]
A -->|skip 1| C["can(1, 3)"]
B -->|take 2| D["can(2, 0) = True"]
B -->|skip 2| E["can(2, 2)"]
C -->|take 2| F["can(2, 1)"]
C -->|skip 2| G["can(2, 3)"]
def canPartition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
def can(i: int, t: int) -> bool:
if t == 0:
return True
if i == len(nums) or t < 0:
return False
return can(i + 1, t - nums[i]) or can(i + 1, t)
return can(0, target)
Complexity: two branches per element → O(2ⁿ) time. At n = 200 this never finishes.
Approach 2 — Memoized top-down
The insight: the state is just (i, t) — index and remaining target. There are n · target such states, so cache them.
from functools import lru_cache
def canPartition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
@lru_cache(maxsize=None)
def can(i: int, t: int) -> bool:
if t == 0:
return True
if i == len(nums) or t < 0:
return False
return can(i + 1, t - nums[i]) or can(i + 1, t)
return can(0, target)
Complexity: O(n·target) time and space.
Approach 3 — Tabulated bottom-up (2-D)
The insight: dp[i][s] = can we make sum s using the first i numbers? Either skip nums[i-1] (dp[i-1][s]) or take it (dp[i-1][s - nums[i-1]]).
Recurrence: dp[i][s] = dp[i-1][s] or (s >= nums[i-1] and dp[i-1][s - nums[i-1]]), with dp[0][0] = True.
def canPartition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
n = len(nums)
dp = [[False] * (target + 1) for _ in range(n + 1)]
dp[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
dp[i][s] = dp[i - 1][s]
if s >= num:
dp[i][s] = dp[i][s] or dp[i - 1][s - num]
return dp[n][target]
Complexity: O(n·target) time, O(n·target) space.
Approach 4 — Space-optimized 1-D (the intended solution)
The insight: dp[i] reads only row i-1, so collapse to a single boolean array over sums. The catch: to use each number at most once, iterate sums downward — going upward would let a number be reused within the same pass (that’s the unbounded knapsack).
def canPartition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for s in range(target, num - 1, -1): # high → low
if dp[s - num]:
dp[s] = True
if dp[target]:
return True
return dp[target]
Walkthrough (nums = [1,5,11,5], target = 11): start dp[0]=True.
- num 1 →
dp[1]=True. reachable {0,1}
- num 5 → sets
dp[6], dp[5]. reachable {0,1,5,6}
- num 11 → sets
dp[11] (from dp[0]). dp[11] is True, so return True.
Complexity: O(n·target) time, O(target) space.
Common pitfalls
- Skipping the odd-total early exit — an odd sum can never split evenly, and it also makes
total // 2 silently wrong.
- Iterating the 1-D sum loop upward, which reuses each number multiple times (solves a different, unbounded problem) and yields false positives.
- Setting the loop lower bound wrong:
range(target, num - 1, -1) stops exactly at num, avoiding negative indices.
- Assuming an empty or single-element array can partition —
[1] returns False (total is odd).
Pattern takeaway
Many “can we split / reach a value” questions reduce to subset-sum: pick a target, then run 0/1 knapsack over a boolean reachability array. The space optimization is a single array iterated from high to low, so each item is used once. The direction matters: iterating low to high reuses items and solves unbounded knapsack instead.