Skip to main content
Bitmask DP

Travelling Salesman

dp[mask][i] = min cost to visit the set of cities in 'mask', ending at city i. Try extending from any city j in the mask to i. The mask tracks which cities are visited. O(2ⁿ × n²) — feasible for n ≤ 20.

O(n² * 2^n)
·
O(n * 2^n)

How It Works

The Held-Karp algorithm solves the Travelling Salesman Problem with bitmask DP. The state dp[mask][i] is the minimum cost to visit exactly the set of cities encoded by mask, ending at city i (whose bit must be set in mask). Transitions extend a tour: from dp[mask][j], move to an unvisited city i, yielding dp[mask | (1<<i)][i] = min(itself, dp[mask][j] + dist[j][i]). The mask makes 'which subset is done' a first-class DP dimension.

There are 2^n × n states, each with O(n) transitions, giving O(2^n × n^2) time and O(2^n × n) space — enormous, yet a massive win over the (n-1)! orderings of brute force, and practical up to roughly n = 20. The final answer takes the best full-mask state, plus the return edge for a closed tour.

Step-by-Step Visualization

TSP: visit all 4 cities with minimum cost
0
0
1
1
2
2
3
3
StartCity 0
mask0001
1/3

Code

Java
static int tsp(int[][] dist) {
  int n = dist.length;
  int[][] dp = new int[1 << n][n];
  for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
  dp[1][0] = 0;

  for (int mask = 1; mask < (1 << n); mask++)
    for (int u = 0; u < n; u++) {
      if ((mask & (1 << u)) == 0 || dp[mask][u] == Integer.MAX_VALUE) continue;
      for (int v = 0; v < n; v++) {
        if ((mask & (1 << v)) != 0) continue;
        int next = mask | (1 << v);
        dp[next][v] = Math.min(dp[next][v], dp[mask][u] + dist[u][v]);
      }
    }

  int full = (1 << n) - 1;
  int ans = Integer.MAX_VALUE;
  for (int i = 0; i < n; i++) if (dp[full][i] != Integer.MAX_VALUE) ans = Math.min(ans, dp[full][i] + dist[i][0]);
  return ans;
}

Tips & Gotchas

1dp[mask][i] = min cost to visit cities in mask, ending at city i
2Try extending from each visited city to each unvisited city
3Final answer: min over all cities of dp[all_visited][i] + cost back to start

Practice Problems

  • 1Find the Shortest Superstring
  • 2Shortest Path Visiting All Nodes
  • 3Minimum Cost to Connect Two Groups of Points
  • 4Travelling Salesman Problem

About the Bitmask DP Pattern

Use a binary number (bitmask) to represent which items have been selected. Bit i is 1 if item i is chosen. This lets you track subsets as DP states — the mask IS the state. Works when n ≤ ~20.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

  • Climbing Stairs
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack
  • Edit Distance
  • House Robber
  • Longest Increasing Subsequence
  • Word Break

Frequently Asked Questions

Why does dp[mask] alone not suffice — why track the end city?

The cost of the next edge depends on where the partial tour currently ends, so subsets with the same visited set but different endpoints have genuinely different futures. Dropping the endpoint dimension merges states that must stay separate and produces wrong answers.

What input size makes bitmask DP feasible?

Memory and time both carry a 2^n factor, so n up to about 20 is the practical ceiling — 2^20 masks times 20 endpoints is roughly 20 million states. If a problem's constraint says n <= 20, that is usually a deliberate hint toward bitmask DP.

How do I iterate transitions efficiently in code?

Loop over masks in increasing order (a superset mask is always numerically larger than its subsets), then over the ending city j with bit set, then over the next city i with bit clear. Bit tricks like mask & (1 << j) and mask | (1 << i) keep the inner loops branch-light.