Partition Equal Subset Sum

Decide whether an array can split into two subsets with equal sums — equivalent to asking whether some subset sums to exactly half the total. A boolean subset-sum DP, processed backwards to avoid reusing an element twice.

Category

Dynamic Programming

Time complexity

O(n·sum)

Space complexity

O(sum)

Pseudocode

if total is odd: impossible
target ← total / 2
dp[0] = true
for each number: for s = target down to number
  dp[s] |= dp[s − number]

Reference implementation

if sum(a) % 2: return False
target = sum(a) // 2
dp = [True] + [False] * target
for num in a:
    for s in range(target, num - 1, -1):
        dp[s] |= dp[s - num]

Open the interactive Partition Equal Subset Sum visualisation →