Bitmask Dynamic Programming

The traveling salesman problem — visit every city exactly once and return home as cheaply as possible — looks like it needs $O(n!)$ brute force over every ordering. But you don't actually need the full order, only two facts at each step: which cities have already been visited, and which one you're currently standing at. Bitmask DP encodes "which subset has been visited" as a single integer, where bit $i$ is 1 if city $i$ has been visited, turning that exponential-looking state into something a table can hold.

The idea: state = (subset visited, current position)

Define $dp[\text{mask}][i]$ as the minimum cost to have visited exactly the set of cities in mask, ending at city $i$. The transition tries extending to every unvisited city $j$:

$$dp[\text{mask} \mid (1\ll j)][j] = \min\big(dp[\text{mask} \mid (1\ll j)][j],\ dp[\text{mask}][i] + \text{cost}(i, j)\big)$$

In words: if you can reach city $i$ having visited exactly mask, then you can reach city $j$ having visited mask plus $j$, at a cost of getting to $i$ plus one more hop. mask | (1 << j) sets bit $j$ — "add city $j$ to the visited set" — and mask & (1 << j) checks whether it's already set. There are $2^n$ possible masks and $n$ possible current cities, so the table has $O(2^n \cdot n)$ entries, and each transition is $O(n)$, giving $O(2^n \cdot n^2)$ total — astronomically better than $O(n!)$ for $n$ around 15-20 ($2^{20} \cdot 20^2 \approx 4\times10^8$ versus $20! \approx 2.4\times10^{18}$), though still only viable for small $n$, which is the honest limit of this technique.

Worked example: 3 cities, tiny TSP

Cities 0, 1, 2, symmetric costs $c(0,1){=}10$, $c(0,2){=}15$, $c(1,2){=}20$, start and must return to city 0. Base case: $dp[\{0\}][0] = 0$ (mask = 001). From there, extend to city 1: $dp[\{0,1\}][1] = dp[\{0\}][0] + c(0,1) = 10$ (mask 011). Extend to city 2: $dp[\{0,2\}][2] = dp[\{0\}][0] + c(0,2) = 15$ (mask 101). From \{0,1\} at city 1, extend to city 2: $dp[\{0,1,2\}][2] = dp[\{0,1\}][1] + c(1,2) = 10+20=30$ (mask 111). From \{0,2\} at city 2, extend to city 1: $dp[\{0,1,2\}][1] = dp[\{0,2\}][2] + c(2,1) = 15+20=35$. Full mask 111 reached at city 2 with cost 30, or city 1 with cost 35; add the return trip home: $30 + c(2,0){=}15 = 45$, or $35 + c(1,0){=}10 = 45$ — both routes tie at 45, which is the answer.

def tsp(cost, n):                     # O(2^n * n^2)
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0                      # start at city 0, only city 0 visited
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == float('inf') or not (mask & (1 << i)):
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue          # already visited
                nmask = mask | (1 << j)
                dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + cost[i][j])
    full = (1 << n) - 1
    return min(dp[full][i] + cost[i][0] for i in range(n))

Where it shows up

Interview staples: traveling salesman itself, "shortest path visiting all nodes" (LeetCode 847), and assignment-style problems where each of $n$ workers must be matched to a distinct task. On a desk, small-scale routing problems — sequencing a handful of trade legs to minimize total market impact, or ordering a short list of rebalancing trades to minimize slippage — fit this pattern exactly when the leg count is small enough for $2^n$ to be tractable.