1. The Held-Karp $O(N^2 2^N)$ TSP Formulation
Given a weighted graph on $N$ vertices $\{0, 1, \dots, N-1\}$ with distance matrix $W[u][v]$, the Traveling Salesperson Problem (TSP) asks for the minimum-weight Hamiltonian cycle visiting every vertex exactly once and returning to start vertex $0$. Since a cycle can be rotated to start at vertex $0$ without loss of generality, we fix $0$ as the start vertex.
Define state $dp[\text{mask}][u]$ for $\text{mask} \in [1, 2^N - 1]$ (with bit $0$ and bit $u$ set) as the minimum cost of a simple walk starting at vertex $0$, visiting the exact subset of vertices encoded by $\text{mask}$, and ending at vertex $u$:
$$dp[\text{mask}][u] = \min_{v \in \text{mask} \setminus \{u\}} \big(dp[\text{mask} \setminus \{u\}][v] + W[v][u]\big)$$Why is the outer loop for (uint32_t mask = 1; mask < (1U << n); ++mask) already a valid topological order? Because removing a bit $u$ (mask ^ (1U << u)) strictly decreases the integer value of mask ($ ext{mask} \setminus \{u\} < \text{mask}$), so every predecessor mask has already been finalized!
Core Invariant — Submask Enumeration in Exact $O(3^N)$ Time
Many partition DPs (such as Minimum Number of Work Sessions, Chromatic Number, or Steiner Tree) require iterating over all submasks $s \subseteq m$ for every mask $m \in [0, 2^N - 1]$. A naive check of all pairs $(m, s)$ takes $O(4^N)$. Instead, using the two's complement decrement trick:
for (int s = m; s > 0; s = (s - 1) & m) { ... }visits only the $2^{\text{popcount}(m)}$ valid submasks of $m$ in descending order!
Proof of $O(3^N)$ Total Time: By the Binomial Theorem, summing $2^k$ over all masks $m$ with $\text{popcount}(m) = k$ gives:
Combinatorially, each of the $N$ bit positions is independently in one of 3 states: (1) in both $m$ and $s$, (2) in $m$ but not $s$, or (3) in neither $m$ nor $s$!
2. Breaking the $O(W \cdot 2^N)$ Barrier: Tuple State DP (Elevator Rides / Bin Packing)
Suppose we want to pack $N \le 20$ items of weights $w_i \le 10^9$ into the minimum number of bins of capacity $W = 10^9$. We cannot put remaining capacity $c \in [0..W]$ in the DP index! Instead, store a lexicographic pair inside the DP value itself: $dp[\text{mask}] = (\text{min\_bins},\; \text{min\_weight\_in\_last\_bin})$, solved in $O(N \cdot 2^N)$ time regardless of how huge $W$ is!
{0, 1, 3} ending at v=1"] -->|"+ W[1][2]"| M1["mask = 01111_2
{0, 1, 2, 3} ending at u=2"] M2["mask = 01011_2
{0, 1, 3} ending at v=3"] -->|"+ W[3][2]"| M1
Hardware Reality — Memory Layout dp[1 << N][N] vs. dp[N][1 << N] & TZCNT Loops
In Held-Karp TSP, the outer loop iterates over mask and the inner loops iterate over set bits $u$ and $v$. If you declare dp[N][1 << N], reading dp[v][mask] for different vertices $v$ jumps by $2^N \times 4$ bytes (4 MB for $N = 20$), causing an L3 cache/TLB miss on every inner transition! Declaring dp[1 << N][N] (flat dp[mask * N + u]) places all $N$ endpoints of the same mask inside a single 80-byte contiguous cache line. Furthermore, iterating only over set bits via for (uint32_t bits = mask; bits; bits &= bits - 1) { int u = __builtin_ctz(bits); ... } halves the number of loop iterations.
3. Complexity Matrix
Trace dimension-by-dimension SOS DP bit-flips F[mask] += F[mask ^ (1<<i)] without overcounting, Broken Profile staircase wavefront domino tiling, and Digit DP tight-prefix automata.
Invariant & State
| Bitmask DP Pattern | State Count | Transitions / State | Total Time Complexity | Practical $N$ Limit (1s) |
|---|---|---|---|---|
Subset / Bin Packing Tuple DP (dp[mask]) |
O(2^N) | O(N) | O(N * 2^N) | $N \le 22$ ($\approx 9 \times 10^7$ ops) |
Held-Karp TSP / Hamiltonian Walk (dp[mask][u]) |
O(N * 2^N) | O(N) | O(N^2 * 2^N) | $N \le 20$ ($\approx 4 \times 10^8$ ops) |
Submask Partition DP (s = (s - 1) & m) |
O(2^N) | O(2^popcount(m)) | O(3^N) | $N \le 15$ ($3^{15} \approx 1.4 \times 10^7$) |
4. Reference C++20 Implementation
#include <algorithm>
#include <cstdint>
#include <utility>
#include <vector>
// 1. Held-Karp O(N^2 * 2^N) Exact Traveling Salesperson Tour (Fixed at start vertex 0)
long long tsp_held_karp(const std::vector<std::vector<long long>>& dist) {
const int n = static_cast<int>(dist.size());
if (n <= 1) return 0;
constexpr long long INF = 1LL << 60;
// Since vertex 0 is always visited first, we only need (N - 1) bits for vertices {1..N-1}
// or full (1 << N) with mask & 1 == 1. Flat layout: dp[mask * n + u] for L1 cache locality.
const std::uint32_t full_mask = (1U << n);
std::vector<long long> dp(static_cast<std::size_t>(full_mask) * n, INF);
dp[1U * n + 0] = 0; // Base case: mask = {0}, standing at vertex 0
for (std::uint32_t mask = 1; mask < full_mask; mask += 2) { // mask += 2 keeps bit 0 always set!
for (std::uint32_t u_bits = mask; u_bits; u_bits &= u_bits - 1) {
int u = __builtin_ctz(u_bits);
long long cur_cost = dp[mask * n + u];
if (cur_cost == INF) continue;
// Push DP to unvisited vertices v
std::uint32_t unvisited = ((full_mask - 1U) ^ mask);
for (std::uint32_t v_bits = unvisited; v_bits; v_bits &= v_bits - 1) {
int v = __builtin_ctz(v_bits);
std::uint32_t next_mask = mask | (1U << v);
dp[next_mask * n + v] = std::min(dp[next_mask * n + v], cur_cost + dist[u][v]);
}
}
}
long long best_tour = INF;
const std::uint32_t all_visited = full_mask - 1U;
for (int u = 1; u < n; ++u) {
best_tour = std::min(best_tour, dp[all_visited * n + u] + dist[u][0]);
}
return best_tour;
}
// 2. O(N * 2^N) Bin Packing / Elevator Rides via Tuple State DP: (num_rides, current_ride_weight)
int min_bins_bitmask_dp(const std::vector<long long>& weights, long long capacity) {
const int n = static_cast<int>(weights.size());
const std::uint32_t limit = 1U << n;
std::vector<std::pair<int, long long>> dp(limit, { n + 1, 0 });
dp[0] = { 1, 0 }; // 1st bin open with 0 weight used
for (std::uint32_t mask = 1; mask < limit; ++mask) {
for (std::uint32_t bits = mask; bits; bits &= bits - 1) {
int i = __builtin_ctz(bits);
auto [rides, used_w] = dp[mask ^ (1U << i)];
std::pair<int, long long> candidate =
(used_w + weights[i] <= capacity)
? std::make_pair(rides, used_w + weights[i])
: std::make_pair(rides + 1, weights[i]);
dp[mask] = std::min(dp[mask], candidate);
}
}
return dp[limit - 1].first;
}Production Pitfall — Infinite Loop in Submask Enumeration When s = 0
In the submask loop for (int s = m; s > 0; s = (s - 1) & m), notice that the loop condition is strictly s > 0! If you write s >= 0, then after visiting s = 0, evaluating (0 - 1) & m = (-1) & m = m wraps right back to m and causes an infinite loop! Always handle the empty submask s = 0 outside the loop if needed.