Subset Sum & Partition — Filling the Boolean DP Table

dp[t] = true if some subset sums to exactly t. Watch each item light up newly reachable sums via dp[t] |= dp[t-v], and the partition target S/2 turn green when reached.

Equal partition reduces to subset-sum at S/2; the same table also counts subsets and finds the most balanced split. Use the controls below to step through each item.

step 0

Items & partition target

Boolean dp table (index t = candidate sum)

Initial: only dp[0] = true (empty subset).
reachable sum newly reachable this item target S/2 target reached
Cell symbols: T = reachable, · = not yet reachable. The leftmost cell dp[0] is always T (the empty subset). The amber cells are exactly the sums that this item just unlocked.
Press Step to begin. We seed dp[0]=true, then process each item v, OR-ing in dp[t-v] for t scanned from high to low so each item is used at most once.

How to read this animation

Each cell dp[t] is a checkbox: is sum t reachable by some subset of the items processed so far? It starts · (false) everywhere except dp[0] = T (the empty subset sums to 0).

Processing item v performs dp[t] |= dp[t-v] for t from the target down to v. Newly-lit cells (amber) are the sums that just became reachable by adding v to a previously reachable sum.

The downward scan matters: if we scanned upward, item v could feed into t-v → t → t+v and be used twice. Scanning high→low guarantees each item is used at most once (0/1 subset, not unbounded knapsack).

The blue-outlined cell is the partition target S/2. The instant it turns green, a subset sums to half the total, so the array splits into two equal halves.

Bitset view: the whole dp row is the bits of one integer B. One item is B |= B << v — a single shift-and-OR processing 64 sums per machine word (the O(n·T/64) speedup).

Equal partition in one line

Compute the total S. If S is odd, there is no equal partition. Otherwise ask the subset-sum question with target S/2: if some subset sums to S/2, the rest sums to S − S/2 = S/2, so the two groups are equal.

That is the entire reduction this animation visualizes: partition into two equal halves ⇔ a subset sums to half the total. Everything else — counting, minimum-difference, k-way — is a re-skin of the same table (see the markdown files).

Why these presets

[1, 5, 11, 5] — the classic LeetCode example. Total 22, target 11, splits as {11} vs {1,5,5}. The target lights green as soon as item 11 is processed.

[1, 2, 3, 5] — total 11 is odd, so the animation short-circuits with NO before filling any table. Parity is an O(1) rejection.

[2, 2, 2, 2] — total 8, target 4, trivially balanced ({2,2} vs {2,2}). Watch sums fill densely.

[3,1,1,2,2,1] — total 10, target 5, perfectly balanced (min difference 0). Several subsets reach 5.

Try your own: type any comma-separated non-negative integers (each ≤ 60, up to 10 items). The animation recomputes the total, the target S/2, and replays the fill. Use Step to inspect one item at a time, Run to autoplay, Reset to restart.
Self-contained visualization. Boolean subset-sum DP, O(n·T) time. Equal partition reduces to subset-sum with target S/2. See junior.md for the running example and professional.md for the correctness proof and the NP-complete / pseudo-polynomial discussion.

Remember the two invariants the animation makes visible: (1) the table only ever grows — once a sum is reachable it stays reachable, because skipping any item is always allowed; and (2) scanning t high→low keeps every item used at most once. If the array’s total is odd, no equal partition can exist, and the animation says so without filling the table. For very large targets the table would be too wide to draw — that is the pseudo-polynomial regime where meet-in-the-middle (small n) or approximation (FPTAS) takes over; see senior.md and professional.md.