vi. Bitmask DP

The state contains a subset of a small ground set ($n\le 20$–$23$), stored as an integer. Bit tricks and submask enumeration are in Bit Tricks and Submasks and SOS; Held–Karp and Hamiltonian paths are in Hamiltonian Paths.

Work	Feasible $n$
$2^n$	25–27
$2^{n}n$	20–23
$2^n{n}^2$	17–19
$3^n$	15–17

Transition shapes

// 1. add one element: assignment, person popcount(mask) gets a job          O(2^n n)
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)) chmin(dp[mask | 1 << j], dp[mask] + cost[i][j]);
}
// 2. split off a group containing the lowest element: set partition / cover O(3^n)
for (int mask = 1; mask < 1 << n; mask++) {
    int low = mask & -mask;
    for (int s = mask; s; s = (s - 1) & mask) if ((s & low) && ok[s]) chmin(dp[mask], dp[mask ^ s] + 1);
}
// 3. aggregate over all submasks: SOS / zeta transform                     O(2^n n)

Proof: $3^n$ total for submask enumeration, and the lowest-element rule

${\sum }_{\text{mask}}{2}^{|\text{mask}|}={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k=3^n$ by the binomial theorem: each element is outside the mask, in the mask but not the submask, or in both. Lowest element: in any partition of mask into groups, exactly one group contains the lowest element of mask; removing that group leaves a partition of the rest. So restricting the first group to those containing low enumerates each partition exactly once (instead of once per ordering of its groups), and the recurrence still covers every partition.

Classic problems

• Assignment ($n\le 20$): pattern 1. Simpler than Hungarian (Assignment) for small $n$.
• TSP / Hamiltonian path ($n\le 20$): dp[mask][i] = shortest path visiting exactly mask, ending at $i$, $O(2^n{n}^2)$ — the extra $n$ over pattern 1 comes from also tracking the current endpoint (Hamiltonian Paths).
• Counting perfect matchings of a bipartite graph (the permanent of a 0/1 matrix): pattern 1 with sums, or Ryser’s formula $\text{perm}(A)=(-1{)}^n{\sum }_S(-1{)}^{|S|}{\prod }_i{\sum }_{j\in S}{a}_{ij}$ in $O(2^{n}n)$ with Gray code.
• Elevator rides (minimum rides of capacity $X$ carrying everyone): dp[mask] = (rides, load of the last ride), minimised lexicographically; add person $j$ to the last ride if it fits, else open a new ride. $O(2^{n}n)$.
• $k$ equal-sum groups: same shape as elevator rides with load modulo target; feasible iff dp[full] reaches load 0.
• Graph colouring / chromatic number: inclusion-exclusion over independent sets in $O(2^{n}n)$ (Graph Coloring).
• Maximum independent set / clique for $n\le 40$–$60$: branch on max-degree vertices or meet in the middle (Maximum Clique).
• Order-dependent costs (“the cost of placing item $j$ depends on which items are already placed”): pattern 1 with cost(mask, j), often precomputed per mask in $O(2^{n}n)$.
• Subset sums of a mask (sum[mask]) in $O(2^n)$: sum[mask] = sum[mask & (mask - 1)] + a[ctz(mask)].

Proof: lexicographic (rides, last load) is a valid DP value for elevator rides

For a fixed set of people already transported (in some order), compare two partial schedules by (number of rides, load of the open last ride). If $A$ has fewer rides than $B$, then $A$ can simulate $B$‘s future: closing $A$‘s current ride and opening a fresh one gives at most $B$‘s ride count with an empty last ride, which is at least as good. With equal ride counts, a smaller last load accepts every future person that $B$‘s last ride accepts. So the lexicographically smallest pair dominates all others, and keeping only it per mask loses nothing. Every schedule is an order of people, which pattern 1 enumerates.

Reducing the state

A compact reference for the shapes these states take:

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

• Derive an index from popcount (the next person, the current position).
• Interchangeable elements: store counts per type instead of a set; $\prod (c_t+1)$ states instead of $2^n$.
• Profile instead of set: when only a frontier matters (grids), see Profile DP.
• Layer by popcount to save memory: only masks of size $k$ and $k+1$ are alive.
• Split the ground set and combine with meet in the middle or SOS: e.g. count subsets of $40$ items with a property that decomposes.
• Flatten to a 1D array (vector<int> indexed by mask, not vector<vector<int>>): noticeably better cache behaviour at $2^{20}$+ states.
• Trade time for space: $2^{20}\times 20$ int is 80 MB, often over the limit; the inclusion-exclusion reformulation (see below) swaps this for $O(2^n{n}^2)$ time and only $O(n^2)$ memory when the DP admits one.
• Accept an approximation when $n$ is simply too big for any exact exponential method: simulated annealing or beam search.

Exponential DPs beyond $2^n$

• Subset convolution / set power series ($f^k$, $\exp$, $\log$ over subsets) in $O(2^n{n}^2)$: counting connected spanning subgraphs, partitions into connected parts (SOS).
• Inclusion-exclusion over subsets replaces “exactly the full set” by alternating sums of “within $S$”: counting Hamiltonian cycles in $O(2^n{n}^3)$ time and polynomial space, Steiner tree, and set cover counting.
• DP over subsets of a separator / tree decomposition: $O(3^{k}n)$ for dominating set, $O(2^{k}n)$ for independent set with treewidth $k$ (Special Graphs).