Partition Problems

Splitting a set or sequence into groups, subject to a constraint. Two very different families share the name.

Family 1: partition a set by value

Subset sum

Can a subset sum to exactly $S$? — 0/1 knapsack with values equal to weights.

bitset<MAXSUM + 1> dp;
dp[0] = 1;
for (int x : a) dp |= dp << x;
bool ok = dp[S];

$O(n\cdot S/64)$ with a bitset — the single most valuable optimisation in this family.

Equal-sum partition

Split into two subsets of equal sum. Feasible iff the total is even and $\mathrm{total}/2$ is a reachable subset sum.

Minimum-difference partition

Minimise $|S_1-S_2|$. Compute all reachable sums up to $\mathrm{total}/2$ and take the largest:

for (int s = total / 2; s >= 0; s--)
    if (dp[s]) { ans = total - 2 * s; break; }

Partition into $k$ equal-sum subsets

NP-hard. For $n\le 20$, bitmask DP: dp[mask] = (number of complete groups, current partial sum). For larger $n$, backtracking with strong pruning — sort descending, skip duplicate values, and abandon a branch as soon as a group cannot be completed.

Balanced partition with huge values

• $n\le 40$: meet in the middle, $O(2^{n/2})$
• $n\le 50$: complete Karmarkar-Karp
• large $n$, approximate: the Karmarkar-Karp differencing heuristic

Family 2: partition a sequence into contiguous segments

The array order is fixed; you choose where to cut.

$dp[i][j]={\min }_{k<i}(dp[k][j-1]+\mathrm{cost}(k,i))$

— best cost for the first $i$ elements in $j$ segments.

for (int j = 1; j <= K; j++)
    for (int i = 1; i <= n; i++)
        for (int k = 0; k < i; k++)
            dp[i][j] = min(dp[i][j], dp[k][j-1] + cost(k, i));

$O(K{n}^2)$ naively. The optimisations:

Condition	Technique	Time
$\mathrm{cost}$ is Monge (monotone argmin)	D&C DP	$O(Kn\log n)$
$\mathrm{cost}$ linear in a parameter	CHT	$O(Kn)$
answer vs $K$ is convex, $K$ huge	Aliens trick	$O(n\log C)$
segment length bounded	monotone queue	$O(Kn)$
minimise the maximum segment cost	binary search + greedy	$O(n\log C)$

Minimax partitioning — always check for this

“Split into $K$ segments minimising the largest segment sum” does not need DP. Binary search the answer $X$ and greedily cut whenever the running sum would exceed $X$; feasible iff the number of segments is $\le K$.

bool feasible(long long X, int K) {
    int segs = 1; long long cur = 0;
    for (long long x : a) {
        if (x > X) return false;
        if (cur + x > X) { segs++; cur = 0; }
        cur += x;
    }
    return segs <= K;
}

$O(n\log (\sum a))$ — vastly simpler and faster than the DP. Recognising minimax objectives is worth a lot.

Family 3: integer partitions (counting)

In how many ways can $n$ be written as a sum of positive integers, order irrelevant? — the partition function $p(n)$.

$p(n)=[x^n]{\prod }_{k\ge 1}\frac{1}{1-x^k}.$

The DP is exactly coin change combinations with coins $\mathrm{1..}n$: $O(n^2)$.

Faster: Euler’s pentagonal number theorem gives
$p(n)={\sum }_{k\ge 1}(-1{)}^{k+1}(p(n-\frac{k(3k-1)}{2})+p(n-\frac{k(3k+1)}{2})),$
which is $O(n\sqrt{n})$ — enough for $n=10^6$.

Variants: partitions into distinct parts, into odd parts (equinumerous, by Euler), into at most $k$ parts, with parts of bounded size. All are small modifications to the coin-change DP or to the generating function.

See also: Knapsack · Subset Sum · Generating Functions · Binary Search on the Answer