Chapter XX Partition

Two equal piles

Sum the lot, divide by two, find a subset that hits exactly that target.

Partition asks whether a multiset of positive integers can be split into two equal-sum halves:

\exists S \subseteq {1, \dots, n} : i \in S \sum a_{i} = i \in / S \sum a_{i} . (1)

Equivalently, (1) holds iff some subset sums to exactly half the total. NP-complete (Karp); the standard subset-sum DP solves it in pseudo-polynomial time

O (n \cdot Σ), Σ = i \sum a_{i} . (2)

Karmarkar-Karp's differencing heuristic gives strong approximate answers. On random inputs near the phase transition — the regime where instances are most often unsolvable — exact algorithms struggle while differencing usually finds optimal partitions. Partition is the textbook reduction source for many other NP-complete problems, including job sequencing, bin packing, and 3-partition.

Figures, in plain terms

(1)

∃ is the exists quantifier — read as "there exists" or "is there a." It asserts that at least one example satisfies what follows.

S ⊆ {1, ..., n} picks a subset of the n indices.

The colon : separates "what we're looking for" from "the property it must satisfy."

After the colon, the property: Σ over i ∈ S of a_i = Σ over i ∉ S of a_i. Two big-sums — one over indices in S, one over indices not in S (the ∉ is "is not in"). The equality demands these sums match.

Reassembled: is there a subset whose sum equals the sum of everything left over? Equivalently, both halves equal half the total.

(2)

Same shape as the knapsack runtime — pseudo-polynomial. n is the count of integers; Σ here stands in for the total sum (the script-Σ on the right of the comma).

So O(n · Σ) is fast when the sums fit comfortably in memory (e.g., total ~10⁶), and intractable when sums are astronomical (10¹⁸+).

The DP solving this just builds a length-(Σ/2 + 1) array of "is this exact sum reachable?" and walks each integer in turn.