The problem
Can the list of positive numbers be split into two groups with equal sums?
Input: [1, 5, 11, 5] Output: true ([1, 5, 5] and [11])
Picture it
Picture a balance scale and a pile of weights. Each pan must hold exactly half the total, so the question becomes: can some of the weights add up to half? We keep a list of every total one pan could reach. Each new weight adds new reachable totals (old total + this weight). If “half” ever becomes reachable, the answer is yes.
How to recognise it
- You must split items into two groups with equal totals, which is the same as finding a subset that sums to exactly half the total.
- Each item is used once (in one group or the other), the 0/1 flavour of a knapsack (a choose-or-skip packing problem).
- The targets are small: up to 200 numbers each at most 100, so half the total is at most 10,000.
- Trying all subsets (2^200) is impossible, but the number of possible sums is small, so track which sums are reachable instead.
- If the total is odd, no split exists, which is the first quick exit.
Start with brute force
Try every subset and check whether its sum is half the total.
def can_partition_brute(nums):
n = len(nums); total = sum(nums)
for mask in range(1 << n):
s = sum(nums[i] for i in range(n) if mask >> i & 1)
if 2 * s == total:
return True
return False
There are 2^n subsets, and each sum costs O(n), so time is O(n × 2^n). With 200 numbers that is about 10^60 subsets, far beyond any limit. Space is O(1) apart from the loop.
From brute force to the idea
- Find the waste. Many different subsets add up to the same sum, and only the sum matters for the target.
- Reduce the question. If the total is odd, return
False. Otherwise the goal is a subset whose sum ishalf = total // 2. - Track reachable sums. Keep a set
reachof every sum some subset of the numbers seen so far can make. Start with{0}(the empty subset). - Add one number at a time. For a new number x, every old sum r gives a new sum
r + x(use x) while the old sums stay (skip x). Ignore sums abovehalf. - Why each number is used once. The set comprehension
{r + x for r in reach ...}is built from the set as it was before this number, so x cannot be added twice in the same step. - Answer.
half in reach.
This is the key idea: keep the set of sums that can be made, grow it by one number at a time, and ask whether half the total appears.
The key idea
Subset-sum: a set (or boolean row) of reachable sums, updated per weight. O(n × total/2).
Python solution
def can_partition(nums):
total = sum(nums)
if total % 2:
return False
half = total // 2
reach = {0} # sums one pan can hold so far
for x in nums:
reach |= {r + x for r in reach if r + x <= half}
return half in reachIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n × 2^n): every subset is summed | O(1): a running sum |
| Reachable sums (shown code) | O(n × total/2): up to n steps, each over at most total/2 distinct sums | O(total/2): the set holds at most that many sums (about 10,000) |
Edge cases
- Odd total (
[3, 1, 1], total 5): returnsFalseimmediately. - One number (
[2]): returnsFalse; half is 1 and no subset makes 1. - Two equal numbers (
[3, 3]): returnsTrue. - Examples:
[1, 5, 11, 5]returnsTrue(11 against 1 + 5 + 5), and[1, 2, 3, 5]returnsFalse. - One big number (
[1, 2, 5]): returnsFalse; the total 8 is even, but no subset makes 4. - 200 numbers of 100: returns
True; the set fills with multiples of 100 and finishes in a fraction of a second.
Common mistakes
- Forgetting the odd-total check, so
[3, 1, 1](total 5, half 2) wrongly returnsTruethrough1 + 1. - Letting a number be used again in the same round, which gives
Truefor[1, 2, 5](by using 2 + 2). - Starting the set empty instead of
{0}, so no sum is ever reachable. - Splitting by sorting and alternating, which is a heuristic and not an exact test.
Given positive numbers and a target k, return whether some subset sums to exactly k. For [3, 34, 4, 12, 5, 2] and k = 9 the answer is True (4 + 5). Describe your approach, then write it if you like.
Compare with our answer
The same reachable-sum set works with k in place of half.
def subset_sum(nums, k):
reach = {0}
for x in nums:
reach |= {r + x for r in reach if r + x <= k}
return k in reach
subset_sum([3, 34, 4, 12, 5, 2], 9) is True and subset_sum([2, 4], 5) is False. Time O(n × k), space O(k).
A strong answer mentions: starting from {0}, capping sums at k, adding x to old sums only (so each number is used once), and that the cost depends on k, not on 2^n.
1. A warehouse has up to 200 parcels, each weighing at most 100 kg, and must load two trucks with exactly equal weight, using every parcel. Which approach fits best?
The reachable-sum set is O(n × total/2), about 2 × 10^6 steps here. Giving the heaviest parcel to the lighter truck is a heuristic that can fail, checking divisibility is necessary but not sufficient, and trying every assignment is exponential.
2. Why is the shown code fast even though there are 2^n subsets?
Only the sum matters, and there are at most about 10,000 distinct sums for these limits. The code does not sort, does not stop early on subsets, and does not skip numbers by size.
3. A learner deletes the if total % 2: return False check. For which input does the function now wrongly return True?
For [3, 1, 1] the total is 5, half becomes 2, and 1 + 1 reaches 2, so the function answers True even though 5 cannot be split into two equal parts. The other inputs have an even total and are already correct.
Score 60% or more and the lesson is marked complete.