Bitmask DP and the Held-Karp TSP

When the state is a set

The two earlier guides in this rung made the DP state an interval or a subtree — ranges and tree nodes are tidy, well-ordered things. But some problems have a state that is genuinely a subset: the set of cities a salesman has already visited, the set of machines currently switched on, the set of people already assigned a task. There is no natural left-to-right order over subsets, and there are 2^n of them over n elements, so at first it looks hopeless to index a table by them. The key realisation is small but powerful: a subset of n items is exactly a string of n bits, and a string of n bits is exactly an integer between 0 and 2^n - 1.

So we encode the subset {0, 2, 3} of items {0, 1, 2, 3} as the bit pattern 1101 — bit i is 1 exactly when item i is in the set — which is the integer 13. This trick, bitmask dynamic programming, lets a plain array `dp[mask]` hold one entry per subset, indexed by an ordinary integer. Set operations become single machine instructions: union is bitwise OR, intersection is AND, 'is item i present?' is `mask & (1<<i)`, and adding item i is `mask | (1<<i)`. The whole apparatus of enumerating subsets from the brute-force rung now has a home inside a DP table.

The Travelling Salesman, set up honestly

The Travelling Salesman Problem (TSP) asks: given n cities and the distance between every pair, find the shortest tour that starts at a city, visits every other city exactly once, and returns home. The naive method is pure brute force: try every ordering of the cities. There are (n-1)! distinct tours (fix the start, then permute the rest), and (n-1)! grows even faster than 2^n — for n = 13 it is already about 479 million orderings. We want to do better, and the question is what work all those orderings share.

Here is the overlap. Suppose two different partial tours both start at city 0, both have visited exactly the set S = {0, 2, 5, 7} of cities, and both currently sit at city 7. Then the cheapest way to finish — to visit all the remaining cities and come home — is identical for both, because the future depends only on which cities still need visiting and where you stand now, not on the order you took to get here. That is the DP state handed to us on a plate: a pair (S, j) meaning 'the set of visited cities is S, and I am currently at city j'. Two partial tours with the same (S, j) are interchangeable from here on — classic overlapping subproblems hiding inside a factorial.

Held-Karp: the recurrence

Let dp[S][j] be the length of the shortest path that starts at city 0, visits exactly the cities in S (where S must contain both 0 and j), and ends at city j. We will fill this table in order of increasing |S|, the number of visited cities, which is the natural transition direction. The base case is the smallest interesting set: dp[{0, j}][j] = dist(0, j) for each j — the one-hop trip straight from the start to j. From there every step adds exactly one newly visited city.

dp[{0,j}][j] = dist(0, j)                       # base: start -> j directly

# fill by increasing |S|; j must be in S, k is the previous city
dp[S][j] = min over k in S, k != j, k != 0 of
               dp[S \ {j}][k] + dist(k, j)

# best full tour: close the loop back to city 0
answer = min over j != 0 of dp[FULL][j] + dist(j, 0)

Read the middle line slowly, because it carries the whole correctness argument. Any shortest path ending at j with visited-set S must have arrived at j from some immediately preceding city k, and at the moment before that final hop it was a shortest path ending at k whose visited-set was exactly S with j removed. If that earlier piece were not itself shortest, we could swap in a cheaper one and beat our supposed optimum — a contradiction. So the optimum over (S, j) is the minimum, over every legal predecessor k, of 'best way to reach k covering S without j' plus the single edge dist(k, j). This is optimal substructure stated precisely: the best whole is built from best parts.

Counting the cost, and reading off the tour

Now the price tag, computed the way the memoization guide taught: (number of distinct states) times (work per state). The states are pairs (S, j): there are 2^n choices of S and, within each, up to n choices of j, so about n * 2^n states. Each state's transition takes a minimum over up to n predecessors k, which is O(n) work. Multiply: O(n^2 * 2^n) time, and O(n * 2^n) space for the table. Compare with brute force's (n-1)! — for n = 20, Held-Karp does roughly 20^2 * 2^20 ~= 4 * 10^8 basic operations, while 19! is about 1.2 * 10^17. The exponential survives, but it has been crushed by an astronomical factor.

The evaluation order is what makes the bitmask encoding pay off. If you fill `dp[S]` for masks in plain increasing integer order, then whenever you compute dp[S][j] the predecessor mask S with j removed is a strictly smaller integer — so it is already filled. No explicit sort by |S| is needed; ordinary integer order respects the dependency for free, because removing a set bit always decreases the number. That tiny coincidence between 'set with one fewer element' and 'smaller integer' is half the reason bitmask DP feels so clean to code.

1. Compute the optimal tour LENGTH first: answer = min over j of dp[FULL][j] + dist(j, 0), and remember the j* that achieved it — that is the last city before returning home.
2. To recover the actual route, walk backwards: at state (FULL, j*) find the predecessor k that achieved dp[FULL][j*] = dp[FULL \ {j*}][k] + dist(k, j*), record j*, then move to state (FULL \ {j*}, k) and repeat.
3. Stop when the set shrinks to {0}; reverse the recorded cities and you have the optimal tour. As always, reconstruction is a cheap walk down one chain of states — far cheaper than the fill that produced the values.

Pitfalls and the honest limits

Three traps catch newcomers. First, the table is two-dimensional — dp[mask][j], not dp[mask] — because two tours covering the same set but ending at different cities have different futures; collapse j out of the state and you get a fast, silently wrong answer, exactly the missing-dimension bug the memoization guide warned about. Second, off-by-one in the bit fiddling: `1 << i` shifts a 1 into position i, and the full set is `(1 << n) - 1`, a common slip. Third, memory, not time, is often the real wall: at n = 22 the table dp[2^22][22] of longs is already a few hundred megabytes, so you hit the limit of RAM before the clock.

And keep the asymptotics honest. O(n^2 * 2^n) is a worst-case scaling statement; it says nothing flattering about absolute speed at, say, n = 25, where 2^25 alone is over 33 million and the n^2 factor multiplies it again. Held-Karp is the best known exact general method for TSP, but 'best known exact' is not 'fast' — for a continent of thousands of cities you abandon exactness entirely and use heuristics or approximation. Knowing precisely where an exact exponential method stops being usable, and what you trade for when you cross that line, is as much a part of mastery as the recurrence itself.