Example 1
ready- Input
nums = [ 1, 5, 11, 5 ]- Expected
true- Why
- [1, 5, 5] and [11] both total 11
Partition Equal Subset Sum
35 min · canPartition()mediumOpen in LeetCode #416 ↗
A pile of workloads can look balanced by count and still be wildly unbalanced by weight. Here you care about the totals.
Given an array of positive integers nums, return true when you can divide its
positions into two groups with the same sum. Return false otherwise.
A partition is a split where every position belongs to exactly one of the two groups. Equal values at different positions still count as separate choices.
A few ground rules:
- You choose each position at most once.
- The order of the values doesn't matter.
- You only return whether an equal split exists; you don't need to return the groups.
Constraints
1 <= nums.length <= 2001 <= nums[i] <= 100
Hints
Check the total first
Two equal integer sums must add to an even total. An odd total lets you answer immediately.
Turn two groups into one target
If the total is T, you only need to ask whether some positions add up to T / 2.
Everything you don't choose automatically forms the other group.
Protect the choose-once rule
Keep a boolean table of reachable sums. Process that table from the target down to the current value so one array position can't be reused during its own update.
Follow-up
Could you recover one actual equal partition while keeping the same time complexity?
Visible cases
Examples
Example 2
ready- Input
nums = [ 1, 2, 3, 5 ]- Expected
false- Why
- the total is odd, so two equal integer sums are impossible
Example 3
ready- Input
nums = [ 1, 1 ]- Expected
true- Why
- put one 1 in each group
Interview signal
Asked at
AmazonGoogleMeta
Equal totals hide a sharper question: can one group reach exactly half of the whole sum? Once you make that turn, this becomes 0/1 subset-sum, where each value may be chosen once or skipped.
Let S be half of the total. If the total is odd, no integer half exists.
Memoized recursion — choose or skip
At position i, either skip nums[i] or spend it toward the remaining sum. Plain
recursion repeats the same (i, remaining) questions. Memoization means caching each
state's answer so that repeated questions return immediately; that turns the search into
top-down dynamic programming (DP).
from functools import cache
def can_partition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
@cache
def search(i: int, remaining: int) -> bool:
if remaining == 0:
return True
if i == len(nums) or remaining < 0:
return False
return search(i + 1, remaining) or search(
i + 1, remaining - nums[i]
)
return search(0, target)Time O(n · S) because there are at most n · S useful states. Space O(n · S)
for the cache, plus at most n recursive calls on the stack.
One-row subset-sum DP
The bottom-up DP stores reachable[s] = True when values processed so far can make
sum s. Sum 0 starts reachable: choose nothing.
For each value, scan sums backward. If you scanned forward, a newly reached sum could feed another update in the same pass, quietly reusing that value more than once.
def can_partition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
reachable = [False] * (target + 1)
reachable[0] = True
for value in nums:
for subtotal in range(target, value - 1, -1):
reachable[subtotal] = (
reachable[subtotal] or reachable[subtotal - value]
)
return reachable[target]Time O(n · S) for n passes across at most S sums. Space O(S) for the one
boolean row.
The backward scan is the signature move of 0/1 subset DP: every update reads only states that existed before the current value was used.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite