Partition Equal Subset Sum

Check whether the values can be split into two groups with equal sums.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Partition Equal Subset Sum: Each number extends a snapshot of previously reachable sums; reaching half the total proves an equal partition.

Input and goalCheck whether the values can be split into two groups with equal sums.

Check the total and seed zeroFor nums = [1, 5, 11, 5], total = 22 is even, so target = 11. The empty subset makes only sum 0 reachable.

next=1105111253

mapLabelpossible sums at or below target 11arithmetictotal=1+5+11+5=22; target=22/2=11branch22 % 2 = 0, continue

possible sums at or below target 110reachable

Recognize it

The input must split into equal-sum groups, so one group must realize exactly half the total; each positive number is either included once or excluded.

Keep true

After processing a prefix of nums, possible contains exactly the sums at most target realizable from that prefix. New sums are computed from an old-set snapshot, so the current number cannot be reused within its own iteration.

Reuse it

Convert a partition condition into a target-reachability problem, then update from a snapshot when each item may be used once. The same state model solves 0/1 knapsack feasibility and constrained subset sums.

Pattern: Subset-sum DP.

Simple idea: The wanted sum is half the total. Keep every sum that can be made from the values processed so far.

def can_partition(nums: list[int]) -> bool:
   total = sum(nums)
   if total % 2:
      return False

   target = total // 2
   possible = {0}
   for num in nums:
      possible |= {value + num for value in possible if value + num <= target}
   return target in possible

Cost: $O(n\times target)$ time and $O(target)$ space.