Bitmask DP & the Travelling Salesman

Encode a subset in the bits of an integer, then DP over subsets — the assignment problem and Held-Karp TSP. · 13 min read

Subsets as integers

When n is small (roughly n ≤ 20), a subset of `n` items fits in the bits of one integer: bit i set means "item i is in the subset". That turns "try every subset" into a loop over 0 … 2ⁿ - 1, and lets a DP be indexed by which items are used so far — dp[mask]. (The bit operations themselves are in the Bit manipulation chapter.)

for (int mask = 0; mask < (1 << n); mask++) {
    int bits = __builtin_popcount(mask);   // how many chosen
    bool has_i = mask & (1 << i);          // is item i in?
    int with_i = mask | (1 << i);          // add item i
    int without = mask & ~(1 << i);        // remove item i
}

Warm-up: the assignment problem

Assign n workers to n distinct tasks at minimum cost. Let dp[mask] be the min cost once the tasks in mask are taken; the worker to place next is popcount(mask). Each transition gives that worker an unused task:

vector<int> dp(1 << n, INF);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] == INF) continue;
    int w = __builtin_popcount(mask);     // next worker
    if (w == n) continue;
    for (int j = 0; j < n; j++)
        if (!(mask & (1 << j)))
            dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[w][j]);
}
return dp[(1 << n) - 1];

Travelling Salesman (Held-Karp)

The Travelling Salesman Problem (TSP) asks for the shortest tour that visits every city once and returns to the start. Brute force tries all (n-1)! tours. Held-Karp is a bitmask DP that does it in O(2ⁿ · n²): let dp[mask][i] be the cheapest path that starts at city 0, visits exactly the cities in mask, and ends at city i.

dp[{0}][0] = 0
for each mask containing 0:
    for i in mask:
        for j not in mask:
            dp[mask | (1<<j)][j] = min(..., dp[mask][i] + dist[i][j])
answer = min over i of dp[full][i] + dist[i][0]   # close the tour

Interactive visualization: Held-Karp: dp[mask][end] over subsets — step through it frame by frame on this page.

Held-Karp cost

2ⁿ subsets × n end-cities — The state is (mask, end).
O(n) transitions per state — Try each next city.
2ⁿ · n² — Multiply.

Result: O(2ⁿ · n²) time, O(2ⁿ · n) space

Iterating submasks

Some bitmask DPs split a set into two parts. Enumerate every submask of a mask efficiently:

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // sub ranges over all non-empty submasks of mask
}

Summed over all masks this is O(3ⁿ) — the basis of partition-style DPs like "minimum number of groups".

Practice: Assignment Problem (Bitmask DP) (Hard) — Assign n workers to n tasks at minimum cost — dp over subsets.

Practice: Travelling Salesman (Held-Karp) (Hard) — Shortest tour visiting every city once — exact, via bitmask DP.