--- title: Bitmask DP module: Dynamic Programming moduleNumber: 8 lessonNumber: 8 order: 808 summary: | When a subproblem depends not on an index or a prefix but on _which subset_ of a small ground set has been used, we can encode that subset as the bits of an integer and index a DP table by it. With $n \le \sim 20$ the $2^n$ subsets fit in a table, turning $\Theta(n!)$ brute force into $O(2^n \cdot \text{poly}(n))$. We meet the bit tricks, the Held–Karp TSP archetype, assignment by mask, subset-sum partitioning, and submask enumeration with its $3^n$ bound. topics: [Dynamic Programming] sources: - book: CLRS ref: "Ch. 15 — Dynamic Programming" - book: Skiena ref: "§ — Exhaustive Search / Dynamic Programming" - book: Erickson ref: "Ch. — Dynamic Programming" practice: - title: 'Shortest Path Visiting All Nodes' slug: shortest-path-visiting-all-nodes difficulty: Hard - title: 'Partition to K Equal Sum Subsets' slug: partition-to-k-equal-sum-subsets difficulty: Medium - title: 'Find the Shortest Superstring' slug: find-the-shortest-superstring difficulty: Hard - title: 'Minimum Cost to Connect Two Groups of Points' slug: minimum-cost-to-connect-two-groups-of-points difficulty: Hard - title: 'Maximum Students Taking Exam' slug: maximum-students-taking-exam difficulty: Hard --- 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. In the traveling salesman problem, the sequence in which the visited cities were reached is irrelevant; what matters is only the **set** of visited cities and the current city. 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 an $n$-bit string, hence 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))$.[^erickson-dp] This encoding builds on the general [principles of dynamic programming](/algorithms/dynamic-programming/principles), and enables 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 $\textsc{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, giving the topological order a subset DP needs. $$ % caption: Subset lattice for $n=3$: each edge adds one bit, so % $\text{mask}\mid(1{\ll}j)>\text{mask}$ — increasing integer order visits every % subset after its proper subsets \begin{tikzpicture}[ every node/.style={draw, minimum size=8mm, inner sep=2pt, font=\footnotesize}, >=stealth, node distance=12mm] \definecolor{acc}{HTML}{2348F2} \node (e) at (3,0) {$000$}; \node (a) at (1,1.4) {$001$}; \node (b) at (3,1.4) {$010$}; \node (c) at (5,1.4) {$100$}; \node (ab) at (1,2.8) {$011$}; \node (ac) at (3,2.8) {$101$}; \node (bc) at (5,2.8) {$110$}; \node[fill=acc!15] (abc) at (3,4.2) {$111$}; \foreach \x in {a,b,c} \draw[->] (e) -- (\x); \draw[->] (a) -- (ab); \draw[->] (b) -- (ab); \draw[->] (a) -- (ac); \draw[->] (c) -- (ac); \draw[->] (b) -- (bc); \draw[->] (c) -- (bc); \draw[->] (ab) -- (abc); \draw[->] (ac) -- (abc); \draw[->] (bc) -- (abc); \node[draw=none, font=\footnotesize, acc] at (7.1,2.1) {add a bit,}; \node[draw=none, font=\footnotesize, acc] at (7.1,1.5) {larger integer}; \end{tikzpicture} $$ ## Held–Karp: the traveling salesman archetype The cleanest bitmask DP is **Held–Karp** for the traveling salesman problem, which is itself [NP-hard](/algorithms/intractability/np-completeness) 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. > **Definition (State).** $dp[\text{mask}][i]$ = the minimum cost of a path that starts at city > $0$, visits _exactly_ the set of cities in `mask`, and currently ends at city > $i$ (so bit $i$ and bit $0$ are both set in `mask`). The exponential savings come from state sharing: 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. $$ % caption: Two visit orders, one state. Both $0{\to}1{\to}2{\to}3$ and % $0{\to}2{\to}1{\to}3$ visit $\{0,1,2,3\}$ and end at $3$, so Held–Karp folds % them into the single state $dp[\,1111\,][3]$ and keeps only the cheaper, % collapsing the factorial of orders. \begin{tikzpicture}[ >=stealth, every node/.style={font=\small}, city/.style={circle, draw, minimum size=6.5mm, inner sep=0}, endc/.style={city, draw=acc, very thick}, st/.style={draw, fill=acc!15, draw=acc, very thick, font=\small, inner sep=3pt}] \definecolor{acc}{HTML}{2348F2} % order A: 0 -> 1 -> 2 -> 3 \node[city] (a0) at (0,0.85) {$0$}; \node[city] (a1) at (1.25,0.85) {$1$}; \node[city] (a2) at (2.5,0.85) {$2$}; \node[endc] (a3) at (3.75,0.85) {$3$}; \draw[->] (a0)--(a1); \draw[->] (a1)--(a2); \draw[->] (a2)--(a3); % order B: 0 -> 2 -> 1 -> 3 \node[city] (b0) at (0,-0.85) {$0$}; \node[city] (b1) at (1.25,-0.85) {$2$}; \node[city] (b2) at (2.5,-0.85) {$1$}; \node[endc] (b3) at (3.75,-0.85) {$3$}; \draw[->] (b0)--(b1); \draw[->] (b1)--(b2); \draw[->] (b2)--(b3); \node[st] (state) at (7.3,0) {$dp[\,1111\,][3]$}; \draw[->, acc, thick] (a3.east) to[out=0,in=150] (state.west); \draw[->, acc, thick] (b3.east) to[out=0,in=210] (state.west); \node[font=\footnotesize, acc, align=center] at (5.3,1.5) {same set, same end:\\one state}; \end{tikzpicture} $$ $$ % caption: $dp[\text{mask}][i]$ = best path visiting the cities in mask, ending at $i$, % extended to a new city $j$ \begin{tikzpicture}[ every node/.style={font=\small}, city/.style={circle, draw, minimum size=7mm, inner sep=0}, bit/.style={draw, minimum size=6mm, inner sep=1pt, font=\small}, >=stealth] \definecolor{acc}{HTML}{2348F2} % path of cities already visited \node[city] (c0) at (0,0) {$0$}; \node[city] (c1) at (1.6,0.5) {$2$}; \node[city] (ci) at (3.2,0) {$i$}; \node[city, draw=acc, thick] (cj) at (5.2,0.6) {$j$}; \draw[->] (c0) -- (c1); \draw[->] (c1) -- (ci); \draw[->, acc, thick] (ci) -- node[above, font=\footnotesize]{\texttt{d(i,j)}} (cj); % the mask as a row of bits below \node[bit, fill=acc!15] (b0) at (0,-1.8) {$1$}; \node[bit, fill=acc!15] (b1) at (0.7,-1.8) {$1$}; \node[bit, fill=acc!15] (b2) at (1.4,-1.8) {$1$}; \node[bit] (b3) at (2.1,-1.8) {$0$}; \node[bit, draw=acc, thick] (b4) at (2.8,-1.8) {$1$}; \node[font=\footnotesize] at (-1.3,-1.8) {mask}; \node[font=\footnotesize, acc] at (2.8,-2.6) {set bit $j$}; \draw[->, acc] (2.8,-2.45) -- (b4.south); \end{tikzpicture} $$ The recurrence extends a path ending at $i$ to a new, previously-unvisited city $j$ by setting bit $j$: $$ dp\brackets{\text{mask} \mid (1{\ll}j)}[j] \;=\; \min_{i \in \text{mask},\ j \notin \text{mask}} \parens{ dp[\text{mask}][i] + d(i, 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$: $$ \text{cost} \;=\; \min_{i} \parens{ dp[F][i] + d(i, 0) }. $$ ```algorithm caption: $\textsc{Held-Karp}(d, n)$ — shortest tour by bitmask DP, $O(2^n n^2)$ $dp[\text{mask}][i] \gets \infty$ for all mask, $i$ $dp[1][0] \gets 0$ // only city $0$ visited, at $0$ for $\text{mask} \gets 1$ to $2^n - 1$ do for $i \gets 0$ to $n - 1$ do if $dp[\text{mask}][i] = \infty$ then continue if $\text{mask}$ does not contain $i$ then continue for $j \gets 0$ to $n - 1$ do if $\text{mask}$ contains $j$ then continue // visited $\text{nmask} \gets \text{mask} \mid (1 \ll j)$ $dp[\text{nmask}][j] \gets \min\parens{dp[\text{nmask}][j],\ dp[\text{mask}][i] + d(i,j)}$ $\textbf{return } \min_i \parens{dp[2^n - 1][i] + d(i, 0)}$ ``` 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. > **Lemma (optimal substructure).** An optimal path realizing $dp[\text{mask}][i]$ > consists of an optimal path realizing $dp[\text{mask} \setminus \{i\}][i']$ for > some $i'$, followed by the edge $(i', i)$. > **Proof.** The path visits the cities of `mask`, ending at $i$; let $i'$ be the > city visited just before $i$. Deleting the final edge leaves a path over > $\text{mask} \setminus \{i\}$ ending at $i'$. If that prefix were not minimal, we > could substitute a cheaper prefix to $i'$ and append $(i', i)$, contradicting the > optimality of the whole; the suffix edge cost $d(i', i)$ does not depend on how > $i'$ was reached. $\qed$ ### A worked instance Take $n = 4$ cities with the symmetric distance matrix $$ d \;=\; \begin{array}{c|cccc} & 0 & 1 & 2 & 3 \\\hline 0 & 0 & 2 & 9 & 10 \\ 1 & 2 & 0 & 6 & 4 \\ 2 & 9 & 6 & 0 & 8 \\ 3 & 10 & 4 & 8 & 0 \end{array} $$ Masks are $4$-bit integers with bit $0$ always set (the tour starts at city $0$). The base case is $dp[0001][0] = 0$. Processing masks in increasing integer order, each state $dp[\text{mask}][i]$ takes the cheapest predecessor $i'$ in $\text{mask} \setminus \{i\}$, and we store that $i'$ as a back-pointer. The reachable entries fill in as follows (only finite entries shown; $\text{mask}$ printed in binary with bit $0$ rightmost): | mask | ends at $i$ | $dp$ | realizing transition | |:--:|:--:|:--:|:--| | $0011$ | $1$ | $2$ | $dp[0001][0] + d(0,1) = 0+2$ | | $0101$ | $2$ | $9$ | $dp[0001][0] + d(0,2) = 0+9$ | | $1001$ | $3$ | $10$ | $dp[0001][0] + d(0,3) = 0+10$ | | $0111$ | $1$ | $15$ | $dp[0101][2] + d(2,1) = 9+6$ | | $0111$ | $2$ | $8$ | $dp[0011][1] + d(1,2) = 2+6$ | | $1011$ | $1$ | $14$ | $dp[1001][3] + d(3,1) = 10+4$ | | $1011$ | $3$ | $6$ | $dp[0011][1] + d(1,3) = 2+4$ | | $1101$ | $2$ | $18$ | $dp[1001][3] + d(3,2) = 10+8$ | | $1101$ | $3$ | $17$ | $dp[0101][2] + d(2,3) = 9+8$ | | $1111$ | $1$ | $21$ | $\min$ over predecessors; winner $dp[1101][3] + d(3,1) = 17+4$ | | $1111$ | $2$ | $14$ | $dp[1011][3] + d(3,2) = 6+8$ | | $1111$ | $3$ | $16$ | $dp[0111][2] + d(2,3) = 8+8$ | Each $dp[1111][i]$ took the minimum over its in-mask predecessors; the rightmost column names the winning one, whose city index is the stored back-pointer. Closing each full-mask entry back to city $0$ gives $\min_i (dp[1111][i] + d(i,0))$: $$ \begin{aligned} i=1:&\quad 21 + d(1,0) = 21 + 2 = 23,\\ i=2:&\quad 14 + d(2,0) = 14 + 9 = 23,\\ i=3:&\quad 16 + d(3,0) = 16 + 10 = 26. \end{aligned} $$ The minimum tour cost is $23$. Reading back-pointers from the closing argmin at $i=2$ ($dp[1111][2]=14$, predecessor $3$; $dp[1011][3]=6$, predecessor $1$; $dp[0011][1]=2$, predecessor $0$) recovers the tour $0 \to 1 \to 3 \to 2 \to 0$ with edge costs $2 + 4 + 8 + 9 = 23$. Starting the traceback at $i=1$ recovers the reverse tour $0 \to 2 \to 3 \to 1 \to 0$, the same cost — expected, since a symmetric-distance tour and its reversal are equal. $$ % caption: Traceback on the worked instance: back-pointers from the closing % argmin $dp[1111][2]$ walk down to lower masks, peeling off one city per % step and rebuilding the tour $0{-}1{-}3{-}2{-}0$ of cost $23$. \begin{tikzpicture}[ every node/.style={font=\small}, st/.style={draw, minimum width=20mm, minimum height=7mm, inner sep=2pt}, hot/.style={st, fill=acc!15, draw=acc, very thick}, >=stealth, node distance=6mm] \definecolor{acc}{HTML}{2348F2} \node[hot] (a) at (0,0) {\texttt{dp[1111][2]=14}}; \node[hot] (b) at (0,-1.3) {\texttt{dp[1011][3]=6}}; \node[hot] (c) at (0,-2.6) {\texttt{dp[0011][1]=2}}; \node[hot] (d) at (0,-3.9) {\texttt{dp[0001][0]=0}}; \draw[->, acc, thick] (a) -- node[right, font=\footnotesize]{pred 3, remove 2} (b); \draw[->, acc, thick] (b) -- node[right, font=\footnotesize]{pred 1, remove 3} (c); \draw[->, acc, thick] (c) -- node[right, font=\footnotesize]{pred 0, remove 1} (d); \node[font=\footnotesize, align=left, anchor=west] at (4.4,-1.95) {list removed nodes\\from bottom to top:\\\texttt{0 - 1 - 3 - 2}, then close\\back to \texttt{0} for cost 23}; \end{tikzpicture} $$ This is just **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](/algorithms/graphs/shortest-paths) of weighted graphs, here the path must cover every node, which is what forces the subset state. ::impl{algo="held_karp,shortest_path_visiting_all_nodes"} ## 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_. 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})$. > **Definition (State).** $dp[\text{mask}]$ = the minimum cost of assigning workers > $0, 1, \dots, \text{popcount}(\text{mask}) - 1$ to the set of tasks in > `mask`. The next worker to place is $k = \text{popcount}(\text{mask})$. The transition gives worker $k$ each task $j$ not yet used: $$ dp\brackets{\text{mask} \mid (1{\ll}j)} \;=\; \min_{j \notin \text{mask}} \parens{ dp[\text{mask}] + c[k][j] }, \qquad k = \text{popcount}(\text{mask}). $$ $$ % caption: Assignment by mask: with $\text{mask}=0110$ two tasks are taken, so % $\text{popcount}=2$ fixes worker $k=2$ as next, branching to a free task ($0$ % or $3$) \begin{tikzpicture}[ every node/.style={font=\small}, bit/.style={draw, minimum size=7mm, inner sep=1pt, font=\small}, >=stealth] \definecolor{acc}{HTML}{2348F2} \node[font=\footnotesize] at (-1.6,0) {mask}; \node[bit] (b3) at (0,0) {$0$}; \node[bit, fill=acc!15] (b2) at (0.75,0) {$1$}; \node[bit, fill=acc!15] (b1) at (1.5,0) {$1$}; \node[bit] (b0) at (2.25,0) {$0$}; \node[font=\footnotesize] at (0,-0.62) {$t_3$}; \node[font=\footnotesize] at (0.75,-0.62) {$t_2$}; \node[font=\footnotesize] at (1.5,-0.62) {$t_1$}; \node[font=\footnotesize] at (2.25,-0.62) {$t_0$}; \node[font=\footnotesize, acc] at (5.0,0.25) {$\text{popcount}=2$}; \node[font=\footnotesize, acc] at (5.0,-0.4) {place worker $k{=}2$}; \node[bit, draw=acc, very thick] (n3) at (0,1.7) {$1$}; \node[bit, draw=acc, very thick] (n0) at (2.25,1.7) {$1$}; \draw[->, acc, thick] (b3) -- node[left, font=\footnotesize]{$+c[2][3]$} (n3); \draw[->, acc, thick] (b0) -- node[right, font=\footnotesize]{$+c[2][0]$} (n0); \node[font=\footnotesize] at (1.125,2.3) {assign a free task}; \end{tikzpicture} $$ 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. ::impl{algo="assignment_mask"} ## 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 state to describe the current group's fill. > **Definition (State).** $dp[\text{mask}]$ = if the set `mask` of elements can be packed into > some whole number of full buckets plus one partial bucket, the value of that > partial bucket modulo $S$; otherwise $\text{mask}$ is infeasible. 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$: $$ \text{if } r + a_i \le S:\quad dp\brackets{\text{mask} \mid (1{\ll}i)} \gets (r + a_i) \bmod 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. ::impl{algo="partition_k_equal_sum"} ## 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: ```algorithm caption: enumerate every submask $\text{sub} \subseteq \text{mask}$ $\text{sub} \gets \text{mask}$ while $\text{sub} > 0$ do // ... use sub and its complement ... $\text{sub} \gets (\text{sub} - 1) \mathbin{\&} \text{mask}$ // empty submask 0 handled after loop ``` 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 total cost across _all_ masks is smaller than the naive bound suggests: > **Lemma.** $\sum_{\text{mask}} (\text{number of submasks of mask}) = 3^n$. > **Proof.** A pair $(\text{mask}, \text{sub})$ with $\text{sub} \subseteq \text{mask}$ > assigns each of the $n$ elements to exactly one of three roles: in `sub`, in > $\text{mask} \setminus \text{sub}$, or in neither. The choices are independent > across elements, so there are $3^n$ such pairs, which is precisely the total > number of (mask, submask) iterations. $\qed$ $$ % caption: a mask, its submasks via the $(\text{sub}-1)\,\&\,\text{mask}$ step, and the % three roles each element plays \begin{tikzpicture}[ every node/.style={font=\small}, bit/.style={draw, minimum size=6mm, inner sep=1pt, font=\small}, >=stealth] \definecolor{acc}{HTML}{2348F2} % mask = 1011 \node[font=\footnotesize] at (-1.5,0) {mask}; \node[bit, fill=acc!15] (m3) at (0,0) {$1$}; \node[bit] (m2) at (0.7,0) {$0$}; \node[bit, fill=acc!15] (m1) at (1.4,0) {$1$}; \node[bit, fill=acc!15] (m0) at (2.1,0) {$1$}; % submask chain \node[font=\footnotesize] at (-1.5,-1.0) {submasks}; \node (s0) at (0.2,-1.0) {$1011$}; \node (s1) at (2.0,-1.0) {$1010$}; \node (s2) at (3.8,-1.0) {$1001$}; \node (s3) at (5.6,-1.0) {$1000$}; \node (s4) at (7.2,-1.0) {\dots}; \node[acc] (s5) at (8.5,-1.0) {$0000$}; \draw[->] (s0) -- (s1); \draw[->] (s1) -- (s2); \draw[->] (s2) -- (s3); \draw[->] (s3) -- (s4); \draw[->] (s4) -- (s5); % step annotation \node[font=\footnotesize, acc] at (3.4,-1.9) {\texttt{sub = (sub - 1) \& mask}}; % three roles \node[font=\footnotesize] at (3.6,-2.9) {\texttt{each} element: in \texttt{sub}, \ in \texttt{mask} \texttt{-} \texttt{sub}, \ or in neither, so $3^n$ pairs}; \end{tikzpicture} $$ 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.[^cormen-dp] ::impl{algo="submask_enumeration"} ## The reach and the ceiling of subset DP Held and Karp published their tour DP in 1962 (Held and Karp, "A dynamic programming approach to sequencing problems", _J. SIAM_ 10), and its $O(2^n n^2)$ bound has never been beaten in the worst case — sixty years on, no $O((2 - \varepsilon)^n)$ exact TSP algorithm is known, and finding one would be a major result. Whether it _can_ be beaten is tied to the **Strong Exponential Time Hypothesis** (SETH); under SETH, several natural covering problems, including some subset DPs here, have no meaningfully faster exact algorithm, so the exponential is likely unavoidable.[^bitmask-beyond] There is one large class where the $2^n$ ceiling drops. When the subset DP is a DP over a graph of small **pathwidth** or **treewidth**, the mask need only track the boundary between processed and unprocessed vertices rather than all vertices; **Maximum Students Taking Exam** exploits this, keeping only the previous _row's_ seating mask. The general statement is Bodlaender's theorem and the "connectivity" DPs over tree decompositions, and the modern refinement is **Cut & Count** (Cygan, Nederlof, Pilipczuk, and coauthors, 2011), which uses randomization and the isolation lemma to solve connectivity problems like Hamiltonicity in $O^\ast(c^{\text{tw}})$ for a small constant $c$ — a better base than the naive $2^{\text{tw}} \cdot \text{tw}$ subset enumeration. The submask/superset machinery in the last section is the entry point to the **subset-sum / subset-convolution** toolkit. The $3^n$ submask enumeration is the brute-force version; the SOS transform (the [DP-optimizations lesson](/algorithms/dynamic-programming/dp-optimizations)) drops the "sum over all submasks" case to $O(2^n n)$, and Björklund, Husfeldt, Kaski, and Koivisto's fast subset convolution (2007) composes two set functions in $O(2^n n^2)$, which is what makes exact graph coloring runnable in $O^\ast(2^n)$ rather than $O^\ast(3^n)$. Beyond these, the practical frontier is heuristic: real routing and scheduling at scale use **branch-and-cut** on integer programs (the Concorde TSP solver has proved optimal tours on tens of thousands of cities) and metaheuristics like Lin–Kernighan, none of which change the worst-case exponent but all of which make the exponential tractable on the instances that actually arise. ## 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<