Bitmask DP

Every dynamic program so far has indexed its subproblems by something ordered: a prefix of an array, a position in a string, a capacity remaining. But some problems have no useful order. The traveling salesman does not care in what sequence you list the cities he has already visited; what matters is only the set of visited cities and where he stands now. The natural subproblem state is therefore a subset of the ground set, and a DP over subsets seems to need a table indexed by subsets, of which there are $2^n$.

A subset of an $n$-element set is exactly an $n$-bit string, which is exactly an integer in $[0,2^n)$. So we encode the subset as the bits of an integer mask and index the DP table by that integer. When $n\le \sim 20$ the $2^n$ masks (up to about a million) fit comfortably in memory, and a $\Theta (n!)$ exhaustive search collapses to $O(2^n\cdot \text{poly}(n))$.¹ This encoding builds on the general principles of dynamic programming, and unlocks a handful of recurring DP shapes.

Bit tricks, compactly

A mask is an integer whose bit $i$ (counting from $0$, least significant) is $1$ iff element $i$ is in the set. The operations we need are all $O(1)$:

• test whether $i\in \text{mask}$: (mask >> i) & 1.
• add $i$: mask | (1 << i); remove $i$: mask & ~(1 << i).
• isolate the lowest set bit: mask & -mask (two's complement makes $-\text{mask}=\sim \text{mask}+1$, which agrees with mask only at and below the lowest $1$).
• popcount (number of set bits): a hardware instruction, or $\text{Kernighan}$'s loop while (m) { m &= m - 1; c++; }, which clears the lowest set bit each step.
• iterate the members: for $i$ from $0$ to $n-1$, test bit $i$.
• the full set is (1 << n) - 1; the empty set is 0.

The whole universe of subsets is the integers $0,1,\dots ,2^n-1$, so a loop for (mask = 0; mask < (1 << n); mask++) visits every subset once. Because mask | (1 << j) > mask whenever bit $j$ was unset, masks that add an element are numerically larger, so iterating masks in increasing order processes every subset after all of its proper subsets, which is exactly the topological order a subset DP needs.

Held–Karp: the traveling salesman archetype

The cleanest bitmask DP is Held–Karp for the traveling salesman problem, which is itself NP-hard so no polynomial algorithm is known. Given $n$ cities and pairwise distances $d(i,j)$, find the shortest tour that starts at city $0$, visits every city exactly once, and returns to $0$. Brute force tries all $(n-1)!$ orderings. The DP observation is that a partial tour is fully summarized by which cities it has visited and where it currently ends; the order in which the visited cities were reached is irrelevant to how cheaply we can finish.

This is where the exponential collapse happens: many distinct visit orders reach the very same $(\text{mask},i)$, and the DP keeps only the cheapest, solving each state once instead of re-exploring every permutation.

The recurrence extends a path ending at $i$ to a new, previously-unvisited city $j$ by setting bit $j$:

The base case is $dp[\{0\}][0]=0$. The answer closes the tour back to the start over the full mask $F=2^n-1$:

Iterating masks in increasing order is valid because $\text{nmask}>\text{mask}$, so every state is finalized before it is read. The table has $2^n\cdot n$ entries and each is relaxed by an inner loop over $n$ candidate predecessors, giving $O(2^n{n}^2)$ time and $O(2^{n}n)$ space. That is exponential, but $2^n{n}^2$ at $n=18$ is about $10^8$, entirely feasible, whereas $17!\approx 3.6\times 10^{14}$ is not.

This is exactly Shortest Path Visiting All Nodes: take $d(i,j)=1$ for graph edges and run the same $dp[\text{mask}][i]$ as a BFS over states $(\text{mask},i)$, where mask is the set of nodes visited so far and the answer is the first time any state with $\text{mask}=F$ is reached. Unlike the single-source shortest paths of weighted graphs, here the path must cover every node, which is what forces the subset state.

Assignment and matching by mask

The same idea solves the assignment problem: assign $n$ tasks to $n$ workers, where worker $k$ doing task $j$ costs $c[k][j]$, minimizing total cost. Here the mask tracks which tasks have been assigned. The key observation is that if we always assign workers in order $0,1,2,\dots$, then once mask is fixed the number of workers already placed is determined: it is exactly $\text{popcount}(\text{mask})$.

The transition gives worker $k$ each task $j$ not yet used:

With base $dp[0]=0$ and answer $dp[2^n-1]$, there are $2^n$ states each with $n$ transitions: $O(2^{n}n)$ time, $O(2^n)$ space, a clean factor of $n$ cheaper than Held–Karp because the current position dimension is replaced by the free information $\text{popcount}(\text{mask})$. Maximum Students Taking Exam is a row-by-row variant: the per-row state is a bitmask of seated columns, and a row's choice is constrained by the previous row's mask plus broken seats.

Subset-sum partitioning over masks

Partition to K Equal Sum Subsets asks whether a multiset can be split into $k$ groups of equal sum $S=(\sum a_i)/k$. Treat the chosen elements as a mask and carry just enough to know how the current group is doing.

Concretely $dp[\text{mask}]$ stores the used capacity of the current bucket, defined when mask is reachable. From a reachable mask with partial fill $r=dp[\text{mask}]$, we may add any element $i\notin \text{mask}$ whose value $a_i$ keeps the bucket within $S$:

where hitting exactly $S$ rolls over to $0$ and opens a fresh bucket. The whole set is partitionable iff $dp[2^n-1]=0$ (every bucket closed exactly). This is $O(2^{n}n)$, the same shape as assignment: $2^n$ masks, $n$ candidate elements per mask, $O(1)$ feasibility check.

Submask enumeration and the $3^n$ bound

Some subset DPs need, for each mask, to consider every way of splitting it into two complementary parts, for instance partitioning a set of cities into groups each served by one route. That requires iterating over all submasks of a given mask. The idiom is:

Subtracting $1$ from sub borrows through its trailing zeros; & mask then snaps the result back inside mask, so the sequence steps through the submasks in strictly decreasing order down to $0$. The cost across all masks is the striking part:

So a DP that, for every mask, loops over all its submasks runs in $O(3^n)$, not the $O(4^n)$ a naive all masks $\times$ all masks bound would suggest. Find the Shortest Superstring and Minimum Cost to Connect Two Groups of Points are submask/mask DPs of this flavor: the latter builds the answer by, for each mask of right-group points, choosing how to cover it given a left point. When the transition is a sum (or min/max) over all submasks of each mask with a fixed contribution per submask, there is an even faster $O(2^{n}n)$ technique, SOS DP (sum over subsets), covered in the DP-optimizations lesson, that beats the $3^n$ enumeration by sharing work across masks.²

Takeaways

• Bitmask DP applies when a subproblem's state is which subset of a small ground set ($n\le \sim 20$) has been used; encode the subset as the bits of an integer and index the table by that mask, giving $2^n$ states.
• The core bit operations (test (mask >> i) & 1, set mask | (1<<i), clear mask & ~(1<<i), lowest bit mask & -mask, popcount) are all $O(1)$, and iterating masks in increasing order is a valid topological order for subset DPs.
• Held–Karp solves TSP with $dp[\text{mask}][i]$ = best path visiting mask ending at $i$, in $O(2^n{n}^2)$ time and $O(2^{n}n)$ space versus $\Theta (n!)$ brute force, and is Shortest Path Visiting All Nodes.
• Assignment and subset-sum partitioning use $dp[\text{mask}]$ alone in $O(2^{n}n)$, exploiting $\text{popcount}(\text{mask})$ to recover the implicit position or bucket state.
• Submask enumeration via sub = (sub - 1) & mask iterates every submask of every mask in total $O(3^n)$, because each element is independently in sub, in the complement, or in neither.