Subset DP

DP over the subsets of a small ground set. The same technique as Bitmask DP — this page collects the patterns from the set point of view.

The state shapes

State	Meaning	Example
dp[mask]	best/count for the set mask	set cover, partitioning
dp[mask][i]	set handled, currently at $i$	TSP
dp[mask][j]	set handled, $j$ extra resource	assignment with budgets
dp[i][mask]	first $i$ items, chosen set mask	small-item knapsack
dp[mask] = pair	(count of full groups, current partial)	$k$ equal-sum partitions

The three transition styles

1. Add one element — $O(2^{n}n)$

for (int mask = 0; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++)
        if (!(mask >> i & 1))
            dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask] + cost(mask, i));

Use popcount(mask) to derive an index. In assignment problems, the number of elements already placed tells you which person/row is next — removing an entire dimension:

int i = __builtin_popcount(mask);            // next person to assign

2. Split into two — $O(3^n)$

for (int mask = 1; mask < (1 << n); mask++)
    for (int s = mask; s; s = (s - 1) & mask)
        dp[mask] = min(dp[mask], dp[s] + dp[mask ^ s]);

See Enumerating Submasks. Fix the lowest set bit in one part to break symmetry.

3. Aggregate over submasks — $O(2^{n}n)$

When the inner sum is a plain subset sum, use SOS DP instead of a $3^n$ loop.

Symmetry breaking

The single most valuable optimisation. When grouping interchangeable items, force a canonical order:

int low = mask & -mask;                       // lowest remaining element
for (int s = mask; s; s = (s - 1) & mask)
    if (s & low) { /* this element leads its group */ }

Without it, a partition into $k$ groups is generated $k!$ times. With it, once.

Worked patterns

Minimum groups covering a set

dp[0] = 0;
for (int mask = 1; mask < (1 << n); mask++) {
    int low = mask & -mask;
    for (int s = mask; s; s = (s - 1) & mask)
        if ((s & low) && valid[s])
            dp[mask] = min(dp[mask], dp[mask ^ s] + 1);
}

Assignment (min cost perfect matching)

for (int mask = 0; mask < (1 << n); mask++) {
    int i = __builtin_popcount(mask);
    if (i == n) continue;
    for (int j = 0; j < n; j++)
        if (!(mask >> j & 1))
            dp[mask | (1<<j)] = min(dp[mask | (1<<j)], dp[mask] + cost[i][j]);
}

$O(2^{n}n)$ — better than the $O(n^3)$ Hungarian algorithm for $n\le 20$, and far easier to write.

Counting Hamiltonian paths

dp[mask][i] as in Held-Karp, summing instead of minimising.

Profile DP on a narrow grid

dp[row][mask] where mask describes the boundary — see Broken Profile DP.

Complexity limits

Shape	Feasible $n$
$O(2^n)$	25
$O(2^{n}n)$	22
$O(2^n{n}^2)$	18-20
$O(3^n)$	16-17
$O(2^n{n}^2)$ memory	~18 (memory usually binds first)

When $n$ is too big

• Split the set in half → meet in the middle, $O(2^{n/2})$.
• Does the set have structure (an interval, a prefix, a tree)? Then the “subset” dimension may collapse.
• Are the items interchangeable? Then a count, not a set, suffices — $n$ states instead of $2^n$.
• Accept an approximation → simulated annealing.

That third point is the most commonly missed: if all items of a given type are identical, replace “which subset is used” with “how many of each type”, turning $2^n$ into a product of small counts.

See also: Bitmask DP · SOS DP · Enumerating Submasks