Bitmask DP — Travelling Salesman (TSP)

Bitmask DP Pattern

When N ≤ 20, represent subsets as bitmasks. Each bit indicates whether an element is "used/visited." State: dp[mask][last], where mask encodes which elements are included. Iterate over all 2^N masks.

When to use: permutation problems, assignment problems, TSP, or any problem where you need to track which subset of N items has been processed.

Recurrence (TSP)

dp[1][0] = 0 // start at city 0
for each mask (increasing):
  for each last city i in mask:
    for each unvisited city j:
      newMask = mask | (1 << j)
      dp[newMask][j] = min(dp[newMask][j],
        dp[mask][i] + dist[i][j])

Mask (binary)	Decimal	Meaning
0001	1	Only city 0 visited
0101	5	Cities 0 and 2 visited
1111	15	All 4 cities visited
mask \| (1<<j)	—	Add city j to visited set
mask & (1<<i)	—	Check if city i is visited

C++ — TSP with Bitmask DP

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    int FULL = (1 << n) - 1;
    vector<vector<int>> dp(FULL+1, vector<int>(n, 1e9));
    dp[1][0] = 0; // start at city 0

    for (int mask = 1; mask <= FULL; mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) continue;
            if (dp[mask][i] >= 1e9) continue;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;
                int next = mask | (1 << j);
                dp[next][j] = min(dp[next][j],
                    dp[mask][i] + dist[i][j]);
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        ans = min(ans, dp[FULL][i] + dist[i][0]);
    return ans;
}

Complexity

Time

O(2^N × N²)

2^N masks × N last cities × N transitions.

Space

O(2^N × N)

DP table: one entry per (mask, city) pair.

Constraint

N ≤ 20

2^20 ≈ 1M states is the practical limit.

vs Brute Force

N! → 2^N × N²

Exponential improvement over trying all permutations.

📝 Notes

▼