Partition

O(n·sum)

The partition problem asks whether a multiset of positive integers can be divided into two groups whose sums are equal. That's possible exactly when the total is even and some subset adds up to half the total — so it reduces to subset sum with target = total / 2. The DP table dp[i][s] marks whether some subset of the first i numbers sums to s; each cell reaches s either without the current number (the row above) or with it (the row above, shifted left by the number). If the total is odd, no split can work and the answer is immediate. It's a classic NP-hard problem with this pseudo-polynomial solution, underlying fair division and load balancing.

DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. Add up the numbers; if the total is odd, no equal split exists.
  2. Otherwise aim for half the total, filling a subset-sum table.
  3. Each cell: reachable without this number, or with it (shifted left by its value).
  4. If the bottom-right cell (sum = half) is reachable, the set splits evenly.

Pseudocode

1partition(nums):                    # O(n·sum)2  total ← sum(nums)3  if total is odd: return false4  half ← total / 25  subset-sum DP: can some subset reach `half`?6    dp[i][s] ← dp[i-1][s] or dp[i-1][s-nums[i]]7  return dp[n][half]                 # split exists ⇔ true