Given an integer array nums, return true if it can be split into two subsets whose sums are equal.
Example
Input nums = [1,5,11,5]
Output true
Key Pointers
If the total sum is odd, an equal split is impossible immediately — no need to search further.
The problem reduces to: can some subset of nums sum to exactly total // 2? That's the classic 0/1 knapsack "subset sum" question.
Tracking a set of currently-reachable sums (rather than a full 2D table) keeps each item from being counted twice in the same subset.
Step-by-Step Analysis
Compute the total sum of nums; if it's odd, return False right away.
Set target = total // 2.
Start a set of reachable sums containing just {0}.
For each number n, add n to every sum already in the reachable set to form new reachable sums (skipping any that exceed target), and merge them in.
Return True if target ends up in the reachable set after processing every number, else False.
Complexity
Time: O(n · target) — Space: O(target)
Code
def canPartition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for n in nums:
reachable |= {s + n for s in reachable if s + n <= target}
return target in reachable
Code Explanation
How the solution above works, piece by piece.
Two equal halves exist only if the total is even; each half must sum to total // 2 (11 here).
So the question becomes: is there a subset that sums to target?
reachable is the set of sums achievable with the numbers seen so far; start with {0} (take nothing).
For each number, every reachable sum can also add it: union in s + n, ignoring sums above the target.
O(n × target) time and space: a set-based 0/1 knapsack.
Visual Walkthrough
Running it on nums = [1, 5, 11, 5]:
Each row lists the sums that can be made so far. After adding 11, the target 11 is reachable (11 alone), so the remaining numbers 1 + 5 + 5 form the other half.