LeetCode 416 · 1-D DP

Partition Equal Subset Sum, explained with a picture

Can a pile of weights balance on a scale?.

Medium1-D DP
▶ Watch it step by step

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

  1. Find the waste. Many different subsets add up to the same sum, and only the sum matters for the target.
  2. Reduce the question. If the total is odd, return False. Otherwise the goal is a subset whose sum is half = total // 2.
  3. Track reachable sums. Keep a set reach of every sum some subset of the numbers seen so far can make. Start with {0} (the empty subset).
  4. 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 above half.
  5. 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.
  6. 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 reach

In 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

ApproachTimeSpace
Brute forceO(n × 2^n): every subset is summedO(1): a running sum
Reachable sums (shown code)O(n × total/2): up to n steps, each over at most total/2 distinct sumsO(total/2): the set holds at most that many sums (about 10,000)

Edge cases

  • Odd total ([3, 1, 1], total 5): returns False immediately.
  • One number ([2]): returns False; half is 1 and no subset makes 1.
  • Two equal numbers ([3, 3]): returns True.
  • Examples: [1, 5, 11, 5] returns True (11 against 1 + 5 + 5), and [1, 2, 3, 5] returns False.
  • One big number ([1, 2, 5]): returns False; 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 returns True through 1 + 1.
  • Letting a number be used again in the same round, which gives True for [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.
Your turn: any target

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.

Check what stuck

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?

2. Why is the shown code fast even though there are 2^n subsets?

3. A learner deletes the if total % 2: return False check. For which input does the function now wrongly return True?

Score 60% or more and the lesson is marked complete.