Partition Equal Subset Sum

Partition Equal Subset Sum is the interview's favourite 0/1 knapsack: each item is taken at most once, and a budget — here, a target sum — limits what fits. The whole family (Target Sum, Last Stone Weight II, the classic value knapsack) uses the same table.

It is also the problem where the space-saving step is a trap: one loop direction is right and the other silently solves a different problem.

The problem

Given a list of positive integers, return True if it can be split into two groups with equal sums, and False otherwise. Every number goes into exactly one group.

• [2, 3, 7, 8, 10] → True. Total 30; 7 + 8 = 15 and 2 + 3 + 10 = 15.
• [1, 2, 5] → False. Total 8, so each half would need 4, and no subset makes 4.

Constraints: 1 ≤ n ≤ 200, 1 ≤ each number ≤ 100.

Clarifying questions

• Must both groups be non-empty? With positive numbers and equal sums they always are.
• Can numbers repeat? Yes, but each position is used once.
• Zero or negative numbers? Not here; negatives would break the "sum up to a target" table.

The reframe

If the total is S, each group must sum to S / 2. So an odd total is False at once. Otherwise the question becomes: is there a subset that sums to exactly S / 2? The other group is simply everything else.

That is 0/1 knapsack with value equal to weight, asking only whether the capacity can be filled exactly.

Approach 1: the simple way — take or skip each number

1def part_rec(nums: list[int]) -> bool:2    """can(i, remaining): can nums[i:] make exactly `remaining`?"""3    total = sum(nums)4    if total % 2:5        return False6    def can(i: int, remaining: int) -> bool:7        if remaining == 0:8            return True9        if i == len(nums) or remaining < 0:10            return False11        return can(i + 1, remaining - nums[i]) or can(i + 1, remaining)  # take or skip12    return can(0, total // 2)

Why it is too slow. It explores up to 2ⁿ take-or-skip choices. When no split exists it must try them all: for [4, 2, 2, …] with 20 numbers it makes 1,384,495 calls, and with 24 numbers 21,769,503. At n = 200 it is hopeless. But the pair (i, remaining) takes at most n × (S / 2 + 1) values — 200 × 10,001 at the limits — so the calls repeat.

The key insight

Only two facts about the past matter: how many numbers you have decided, and what sum they make. Which exact numbers made that sum is irrelevant. So:

dp[i][s] = True if some subset of the first i numbers sums to exactly sdp[i][s] = dp[i - 1][s]                       (skip number i)        or dp[i - 1][s - nums[i - 1]]         (take it, if it fits)dp[i][0] = True        — the empty subset makes 0

The i − 1 in the "take" branch is what makes it 0/1: after taking number i, you look at a row that no longer offers it. The combine step is or, because the question is "is it possible".

Approach 2: memoisation

1from functools import cache23def part_memo(nums: list[int]) -> bool:4    total = sum(nums)5    if total % 2:6        return False7    @cache8    def can(i: int, remaining: int) -> bool:9        if remaining == 0:10            return True11        if i == len(nums) or remaining < 0:12            return False13        return can(i + 1, remaining - nums[i]) or can(i + 1, remaining)14    return can(0, total // 2)

At most n × (S / 2 + 1) states, O(1) each: O(n × S) time and space. The or stops early once a subset is found.

Approach 3: the full table

1def part_table(nums: list[int]) -> bool:2    total = sum(nums)3    if total % 2:4        return False5    target, n = total // 2, len(nums)6    dp = [[False] * (target + 1) for _ in range(n + 1)]   # dp[i][s]7    for i in range(n + 1):8        dp[i][0] = True                                    # empty subset makes 09    for i in range(1, n + 1):10        x = nums[i - 1]11        for s in range(1, target + 1):12            dp[i][s] = dp[i - 1][s] or (x <= s and dp[i - 1][s - x])13    return dp[n][target]

O(n × target) time and space: at the limits the total is at most 200 × 100 = 20,000, so the table has 200 × 10,000 = 2 million cells.

Approach 4: one row, backwards

Row i reads only row i − 1. Keep one row, reach[s], and update it for each number — but loop s from high to low.

1def can_partition(nums: list[int]) -> bool:2    """0/1 knapsack in one row: is there a subset summing to half the total?"""3    total = sum(nums)4    if total % 2:5        return False6    target = total // 27    reach = [True] + [False] * target        # reach[s]: some subset so far makes s8    for x in nums:9        for s in range(target, x - 1, -1):   # backwards: each x used at most once10            if reach[s - x]:11                reach[s] = True12        if reach[target]:13            return True                      # stop as soon as half is reachable14    return reach[target]

Why backwards? When reach[s] reads reach[s − x], the smaller index must still hold the value from before x was considered. Going down, s − x has not been touched in this pass yet. Going up, it may already be True because of x, and then x is counted twice.

Dry run on [2, 3, 7, 8, 10], target 15 — the reachable sums after each number:

15 becomes reachable when 8 is added to 7, so the function returns True without looking at 10. Complexity: O(n × target) time, O(target) space.

The forwards bug, on two numbers. Take [1, 5]: total 6, target 3, and the true answer is False. Loop forwards for x = 1: reach[1] becomes True from reach[0], then reach[2] from the new reach[1], then reach[3] from the new reach[2]. The single 1 has been used three times, and the function returns True. Forwards is the right loop for unbounded knapsack (Coin Change), where reuse is the point — so the direction alone decides which problem you solved.

A compact alternative in Python: keep the reachable sums as bits of one integer, reach |= reach << x for each number, and test bit target. Same O(n × target) bound, but the inner loop runs inside the integer shift, so it is much faster in practice.

Edge cases

• Odd total — False before any table is built.
• One number — its total is odd or, if even, half of it cannot be made from nothing else: False.
• A number bigger than half the total — it can never be in the half-sum subset; the loop range range(target, x - 1, -1) is empty for it, so it is skipped naturally.
• Large values — the cost depends on the size of the target, not on n alone. This is called pseudo-polynomial: with values up to 10⁹, the table is impossible even for five numbers.

Follow-ups

• Classic knapsack with values — best[c] = max(best[c], best[c − w] + v), same backwards loop. With weights [1, 3, 4], values [15, 20, 30] and capacity 4, the answer is 35 (the first two items), as in the diagram's table.
• Signs + and − to reach a target (Target Sum) — if P is the sum of the + numbers, P − (total − P) = target, so P = (total + target) / 2. Count the subsets with that sum: the same table with + instead of or, and dp[0] = 1.
• Split to make the two sums as close as possible (Last Stone Weight II) — build reach up to half the total, then take the largest reachable s; the answer is total − 2s.