---
title: "Held–Karp: Hamilton in O(2ⁿn²)"
summary: Exponential, but the right exponential — bitmask DP for Hamiltonian paths, cycles and the travelling salesman.
difficulty: hard
tags: [DP, bitmask, TSP]
time: 2^n n^2
space: 2^n n
prereq: [euler/hamilton-theorems]
see: [complexity/escape, structures/segment-tree]
---

Deciding Hamiltonicity is NP-complete, so we settle for exponential — and the exact exponent is the whole sport. The classic is $O(2^n n^2)$ time, $O(2^n n)$ memory, via "which subsets, ending where?".

:::definition label="State"
$\operatorname{dp}[M][v] = $ "true $\iff$ there is a path that visits **exactly** the vertices of $M$ and ends at $v$, with $v \in M$".
Transition: $\operatorname{dp}[M][v] = \bigvee_{u \in M \setminus \{v\}, \; uv \in E} \operatorname{dp}[M \setminus \{v\}][u]$.
Answer: $\bigvee_u \operatorname{dp}[V][u] \wedge (u \sim s)$ for a cycle through a fixed start $s$; the path version is $\bigvee_{u,v} \operatorname{dp}[V][u]$ (any endpoints).
:::

```cpp hamilton.cpp
const int MAXN = 20;
bool dp[1 << MAXN][MAXN];
int main() {
    int n, m; cin >> n >> m;
    vector<int> adj(n);                       // bitmask of neighbours
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; --u; --v;
        adj[u] |= 1 << v; adj[v] |= 1 << u;
    }
    for (int s = 0; s < n; s++) dp[1 << s][s] = 1;
    for (int M = 1; M < (1 << n); M++)
        for (int v = 0; v < n; v++) if (dp[M][v] && (M >> v & 1)) {
            int rest = adj[v] & ~M;             // only unvisited neighbours
            while (rest) {
                int u = __builtin_ctz(rest); rest &= rest - 1;
                dp[M | 1 << u][u] = 1;
            }
        }
    int all = (1 << n) - 1;
    for (int v = 0; v < n; v++)
        if (dp[all][v] && (adj[v] & 1)) { cout << "YES\n"; return 0; }
    cout << "NO\n";
}
```

:::note title="Why the inner loop is `adj[v] & ~M`"
Iterating $u$ over all $n$ vertices costs $2^n n^2$; iterating only over *unvisited neighbours* via `ctz` bit-extraction costs $\sum_M \sum_{v \in M} \deg_{\bar M}(v)$, which is bounded by $2^n m / 2$ in the worst case but typically much smaller — and for dense graphs, the bit-OR form
`reach[M] |= ...` reduces it to $O(2^n \cdot n / 64)$ per step with a `bitset`.
:::

## TSP, i.e. the weighted version
Same state, but keep the *cost* and take min: $\operatorname{dp}[M][v] = \min_u \operatorname{dp}[M \setminus \{v\}][u] + w(u,v)$.

```cpp tsp.cpp
int dp[1 << 20][20];                            // 4 * 10^6 ints: fits
for (int v = 1; v < n; v++) dp[1][v] = w(0, v);  // start fixed at 0
for (int M = 1; M < 1 << (n-1); M++)
    for (int v = 1; v < n; v++) if (M >> (v-1) & 1)
        for (int u = 1; u < n; u++) if (!(M >> (u-1) & 1))
            dp[M | 1 << (u-1)][u] = min(dp[M | 1 << (u-1)][u], dp[M][v] + w(v, u));
int ans = INF;
for (int v = 1; v < n; v++) ans = min(ans, dp[(1 << (n-1)) - 1][v] + w(v, 0));
```

:::props title="What the numbers really allow"
- $n \le 20$: $2^{20} \cdot 400 \approx 4 \cdot 10^8$ naive inner steps — tight, so use the bit tricks or drop to $n \le 18$;
- memory $2^n \cdot n$: at $n = 20$ that is $4 \times 10^6$ cells = 16 MB for `int`, 32 MB for `long long` — check the limit *before* choosing the state,
- $n \le 25$: meet in the middle on paths, or Held–Karp with `unordered`-style pruning;
- metric TSP: Christofides gives $\frac{3}{2}$-approx in poly time (MST + min-weight perfect matching on odd-degree vertices — which is why @matching/general-matching matters), and the *path* version is even a bit better; for general weights no $2-\epsilon$ approximation exists unless P = NP.
:::

:::example title="Counting Hamiltonian cycles, not just finding one"
Replace `bool` by `long long mod M` and $\bigvee$ by $+$. The count mod $2$ is the interesting theoretical object (it relates to the determinant of the adjacency matrix over $\mathbb{F}_2$ — @matrices/matrix-tree has the parallel argument for spanning trees).
:::

:::warning title="Three state-design mistakes"
1. Forgetting to fix a start vertex for the *cycle* version: then every cycle is counted $n$ times (or $2n$ if you care about direction) and the boolean version stays correct but the *count* is wrong.
2. Transition order: iterate masks by increasing popcount, or at least ensure $M \setminus \{v\} < M$ numerically (true for bitmasks, so a plain increasing loop is fine — but do not "optimise" by iterating vertices in the outer loop unless you keep that invariant).
3. Using $\operatorname{dp}[M][v]$ = "visits *at least* $M$". Half-open vs exact-subset semantics changes the answer.
:::

:::problems
- [[CSES 1690]] Hamiltonian Flights | https://cses.fi/problemset/task/1690 | core | bitmask DP, directed
- [[CSES 1136]] Counting Paths | https://cses.fi/problemset/task/1136 | core | paths on a tree, contrast
:::

:::note title="Why this is a 'proper' exponential and not a brute force"
Brute force is $O(n!)$; Held–Karp is $O(2^n n^2)$ — the improvement comes from *memoising over subsets*, i.e. realising that "which vertices are used and where am I" is all the future cares about. That single observation is the same one behind every "DP over bitmasks" problem (assignment, scheduling with conflicts, subset convolution warm-ups), and the way to recognise it is a constraint of the form "each item used at most once".
:::