These are the notes for DSA episode 77. A delivery rider leaves the restaurant (city 0), must reach every drop point exactly once and come back. Which order makes the round trip shortest? We try nearest point first (a wrong answer on screen: 125 instead of 80), then every order with backtracking (correct, then Time Limit Exceeded on 14 cities), see that two orders which visited the same set and stand at the same city have the same future, store that set in the bits of an int, and build dp[mask][i] (the Held-Karp algorithm). Then 18 cities in a tenth of a second and three real bugs, including an integer overflow and a real compile error. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| The delivery rider | In code |
|---|---|
| The restaurant | city 0 |
| The drop points | cities 1 .. n − 1 |
| The distance from one point to another | d[i][j] |
| Every drop point once, then back | a tour: a cycle through all cities |
| The shortest round trip | the minimum total distance |
Every word, from zero
- Travelling salesman problem (TSP): visit every city exactly once and return to the start, with the least total distance.
- Tour: one such round trip, e.g.
0 → 1 → 3 → 2 → 0. - Distance matrix:
d[i][j]is the distance from cityito cityj. - Nearest neighbour: a greedy rule: always go to the closest unvisited city.
- Backtracking: mark a choice, recurse, then undo it to try the next one.
- Bit: a single 0 or 1. An
inthas 32 bits; bitjis worth2^j. - Bitmask: an int whose bits say which items are in a set: bit
jis 1 if cityjis in the set.{0, 1, 3}→1011→ 11. 1 << j(left shift): a 1 movedjplaces left: only bitjset.1 << 3 = 8 = 1000.&(bitwise AND): keeps bits that are 1 in both.(mask & (1 << j)) != 0asks "is city j in the set?".|(bitwise OR): sets a bit.mask | (1 << j)adds cityj.- Full mask:
(1 << n) − 1, allnbits set: every city visited. - State:
(mask, i): which cities are visited, and where we stand. - INF: a stand-in for "not reached yet", here
Integer.MAX_VALUE. - Overflow: an
intresult past2³¹ − 1wraps around to a negative number. - Held-Karp: the name of this bitmask DP for TSP (1962).
Problem statement
Given an n × n distance matrix, return the length of the shortest tour that starts at city 0, visits every city exactly once, and returns to 0. Exact solutions are exponential, so n is small (about 16 to 20).
| Cities | Distance matrix | Answer | Best tour |
|---|---|---|---|
| a (4) | {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}} |
80 | 0 → 1 → 3 → 2 → 0 |
| b (5) | {{0,40,5,5,5},{40,0,30,25,40},{5,30,0,25,30},{5,25,25,0,15},{5,40,30,15,0}} |
80 | 0 → 4 → 3 → 1 → 2 → 0 |
| one city | {{0}} |
0 | nowhere to go |
| two cities | {{0,7},{7,0}} |
14 | there and back |
Obvious idea 1: nearest point first
import java.util.*;
public class Main {
static int tsp(int[][] d) {
int n = d.length, city = 0, total = 0;
boolean[] seen = new boolean[n];
seen[0] = true;
for (int step = 1; step < n; step++) {
int next = -1;
for (int j = 0; j < n; j++)
if (!seen[j] && (next == -1 || d[city][j] < d[city][next])) next = j;
total += d[city][next];
seen[next] = true;
city = next;
}
return total + d[city][0];
}
public static void main(String[] args) {
int[][] a = {{0, 10, 15, 20}, {10, 0, 35, 25},
{15, 35, 0, 30}, {20, 25, 30, 0}};
int[][] b = {{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40},
{5, 30, 0, 25, 30}, {5, 25, 25, 0, 15},
{5, 40, 30, 15, 0}};
System.out.println(tsp(a));
System.out.println(tsp(b));
}
}
80
125
125 instead of 80 for b. The restaurant is 5 away from cities 2, 3 and 4 but 40 from city 1; nearest-first leaves city 1 for last and then pays 40 to ride home from it.
Obvious idea 2: try every order
import java.util.*;
public class Main {
static int tsp(int[][] d) {
boolean[] seen = new boolean[d.length];
seen[0] = true;
return go(d, 0, 1, seen);
}
static int go(int[][] d, int city, int count, boolean[] seen) {
if (count == d.length) return d[city][0];
int best = Integer.MAX_VALUE;
for (int j = 0; j < d.length; j++)
if (!seen[j]) {
seen[j] = true;
best = Math.min(best, d[city][j] + go(d, j, count + 1, seen));
seen[j] = false;
}
return best;
}
public static void main(String[] args) {
int[][] a = {{0, 10, 15, 20}, {10, 0, 35, 25},
{15, 35, 0, 30}, {20, 25, 30, 0}};
int[][] b = {{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40},
{5, 30, 0, 25, 30}, {5, 25, 25, 0, 15},
{5, 40, 30, 15, 0}};
System.out.println(tsp(a));
System.out.println(tsp(b));
System.out.println(tsp(new int[][]{{0}}));
System.out.println(tsp(new int[][]{{0, 7}, {7, 0}}));
}
}
80
80
0
14
Correct. Now 14 cities with random distances:
import java.util.*;
public class Main {
static int[][] random(int n) {
Random rnd = new Random(1);
int[][] d = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
d[i][j] = d[j][i] = rnd.nextInt(100) + 1;
return d;
}
static int tsp(int[][] d) {
boolean[] seen = new boolean[d.length];
seen[0] = true;
return go(d, 0, 1, seen);
}
static int go(int[][] d, int city, int count, boolean[] seen) {
if (count == d.length) return d[city][0];
int best = Integer.MAX_VALUE;
for (int j = 0; j < d.length; j++)
if (!seen[j]) {
seen[j] = true;
best = Math.min(best, d[city][j] + go(d, j, count + 1, seen));
seen[j] = false;
}
return best;
}
public static void main(String[] args) {
for (int n : new int[]{14}) {
int[][] d = random(n);
long t0 = System.nanoTime();
int c = tsp(d);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(n + " cities: " + c + ", " + ms + " ms");
}
}
}
(no output: still running after 25 s: Time Limit Exceeded)
Why is it slow?
- After city 0 there are 13 choices, then 12, ...:
13! ≈ 6.2 billionorders. 0 → 1 → 2 → 3 → ...and0 → 2 → 1 → 3 → ...both visited{0, 1, 2, 3}and stand at 3: their futures are identical. Only the shorter one matters.- So the state is
(visited set, current city):2ⁿ × nstates, about 230,000 for 14 cities.
The key insight: a set inside an int
| Set | Bits (city 3 2 1 0) | Int |
|---|---|---|
{0} |
0001 |
1 |
{0, 1} |
0011 |
3 |
{0, 1, 3} |
1011 |
11 |
{0, 1, 2, 3} |
1111 |
15 = (1 << 4) − 1 |
dp[mask][i] = shortest path from 0 through exactly the cities in mask, ending at i
dp[1][0] = 0 everything else INF
from (mask, i), for every j not in mask:
dp[mask | 1 << j][j] = min(dp[mask | 1 << j][j], dp[mask][i] + d[i][j])
answer = min over i of dp[full][i] + d[i][0]
Adding a city only makes the mask bigger, so looping mask upward finishes every state before it is extended.
By hand: example a
| Mask | Set | End at 0 | End at 1 | End at 2 | End at 3 |
|---|---|---|---|---|---|
0001 |
{0} | 0 | · | · | · |
0011 |
{0, 1} | · | 10 | · | · |
1011 |
{0, 1, 3} | · | 45 | · | 35 |
1111 |
all | · | 70 | 65 | 75 |
Ride home: 70 + 10 = 80, 65 + 15 = 80, 75 + 20 = 95 → 80.
Solution in Java
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static int tsp(int[][] d) {
int n = d.length, full = 1 << n;
int[][] dp = new int[full][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;
for (int mask = 1; mask < full; mask++)
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF) continue;
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int next = mask | (1 << j);
dp[next][j] = Math.min(dp[next][j], dp[mask][i] + d[i][j]);
}
}
int ans = INF;
for (int i = 0; i < n; i++)
ans = Math.min(ans, dp[full - 1][i] + d[i][0]);
return ans;
}
public static void main(String[] args) {
int[][] a = {{0, 10, 15, 20}, {10, 0, 35, 25},
{15, 35, 0, 30}, {20, 25, 30, 0}};
int[][] b = {{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40},
{5, 30, 0, 25, 30}, {5, 25, 25, 0, 15},
{5, 40, 30, 15, 0}};
System.out.println(tsp(a));
System.out.println(tsp(b));
System.out.println(tsp(new int[][]{{0}}));
System.out.println(tsp(new int[][]{{0, 7}, {7, 0}}));
}
}
80
80
0
14
The 14 cities that timed out, and 16 and 18 cities:
import java.util.*;
public class Main {
static int[][] random(int n) {
Random rnd = new Random(1);
int[][] d = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
d[i][j] = d[j][i] = rnd.nextInt(100) + 1;
return d;
}
static final int INF = Integer.MAX_VALUE;
static int tsp(int[][] d) {
int n = d.length, full = 1 << n;
int[][] dp = new int[full][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;
for (int mask = 1; mask < full; mask++)
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF) continue;
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int next = mask | (1 << j);
dp[next][j] = Math.min(dp[next][j], dp[mask][i] + d[i][j]);
}
}
int ans = INF;
for (int i = 0; i < n; i++)
ans = Math.min(ans, dp[full - 1][i] + d[i][0]);
return ans;
}
public static void main(String[] args) {
for (int n : new int[]{14, 16, 18}) {
int[][] d = random(n);
long t0 = System.nanoTime();
int c = tsp(d);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(n + " cities: " + c + ", " + ms + " ms");
}
}
}
14 cities: 152, 21 ms
16 cities: 169, 35 ms
18 cities: 170, 79 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Travelling salesman, bitmask DP (Held-Karp):
// dp[mask][i] = shortest path from city 0 through exactly the cities in mask, ending at city i.
int tsp(const vector<vector<int>>& d) {
const int INF = INT_MAX;
int n = d.size(), full = 1 << n;
vector<vector<int>> dp(full, vector<int>(n, INF));
dp[1][0] = 0;
for (int mask = 1; mask < full; mask++)
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF) continue; // not reached: never add to INF
for (int j = 0; j < n; j++) {
if (mask & (1 << j)) continue; // j already visited
int next = mask | (1 << j);
dp[next][j] = min(dp[next][j], dp[mask][i] + d[i][j]);
}
}
int ans = INF;
for (int i = 0; i < n; i++)
if (dp[full - 1][i] != INF) ans = min(ans, dp[full - 1][i] + d[i][0]); // the ride home
return ans;
}
int main() {
vector<vector<int>> a = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
vector<vector<int>> b = {{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40}, {5, 30, 0, 25, 30}, {5, 25, 25, 0, 15}, {5, 40, 30, 15, 0}};
cout << tsp(a) << "\n" << tsp(b) << "\n";
cout << tsp({{0}}) << "\n" << tsp({{0, 7}, {7, 0}}) << "\n";
}
80
80
0
14
The same solution in Python
# Travelling salesman, bitmask DP (Held-Karp):
# dp[mask][i] = shortest path from city 0 through exactly the cities in mask, ending at city i.
def tsp(d):
INF = float("inf")
n = len(d)
full = 1 << n
dp = [[INF] * n for _ in range(full)]
dp[1][0] = 0
for mask in range(1, full):
for i in range(n):
if dp[mask][i] == INF:
continue
for j in range(n):
if mask & (1 << j): # j already visited
continue
nxt = mask | (1 << j)
dp[nxt][j] = min(dp[nxt][j], dp[mask][i] + d[i][j])
return min(dp[full - 1][i] + d[i][0] for i in range(n)) # the ride home
a = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
b = [[0, 40, 5, 5, 5], [40, 0, 30, 25, 40], [5, 30, 0, 25, 30], [5, 25, 25, 0, 15], [5, 40, 30, 15, 0]]
for d in (a, b, [[0]], [[0, 7], [7, 0]]):
print(tsp(d))
80
80
0
14
Three real bugs
Bug 1: the ride home is forgotten. That's the shortest path through every city, not a round trip.
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static int tsp(int[][] d) {
int n = d.length, full = 1 << n;
int[][] dp = new int[full][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;
for (int mask = 1; mask < full; mask++)
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF) continue;
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int next = mask | (1 << j);
dp[next][j] = Math.min(dp[next][j], dp[mask][i] + d[i][j]);
}
}
int ans = INF;
for (int i = 0; i < n; i++)
ans = Math.min(ans, dp[full - 1][i]);
return ans;
}
public static void main(String[] args) {
int[][] a = {{0, 10, 15, 20}, {10, 0, 35, 25},
{15, 35, 0, 30}, {20, 25, 30, 0}};
int[][] b = {{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40},
{5, 30, 0, 25, 30}, {5, 25, 25, 0, 15},
{5, 40, 30, 15, 0}};
System.out.println(tsp(a));
}
}
65
Bug 2: unreached states are not skipped. INF + d[i][j] overflows to a huge negative number, which wins every minimum.
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static int tsp(int[][] d) {
int n = d.length, full = 1 << n;
int[][] dp = new int[full][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;
for (int mask = 1; mask < full; mask++)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int next = mask | (1 << j);
dp[next][j] = Math.min(dp[next][j], dp[mask][i] + d[i][j]);
}
}
int ans = INF;
for (int i = 0; i < n; i++)
ans = Math.min(ans, dp[full - 1][i] + d[i][0]);
return ans;
}
public static void main(String[] args) {
int[][] a = {{0, 10, 15, 20}, {10, 0, 35, 25},
{15, 35, 0, 30}, {20, 25, 30, 0}};
int[][] b = {{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40},
{5, 30, 0, 25, 30}, {5, 25, 25, 0, 15},
{5, 40, 30, 15, 0}};
System.out.println(tsp(a));
}
}
-2147483629
Bug 3: a bit test without brackets. In Java, != binds tighter than &, so 1 << j != 0 is computed first (a boolean), and int & boolean doesn't compile.
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static int tsp(int[][] d) {
int n = d.length, full = 1 << n;
int[][] dp = new int[full][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;
for (int mask = 1; mask < full; mask++)
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF) continue;
for (int j = 0; j < n; j++) {
if (mask & 1 << j != 0) continue;
int next = mask | (1 << j);
dp[next][j] = Math.min(dp[next][j], dp[mask][i] + d[i][j]);
}
}
int ans = INF;
for (int i = 0; i < n; i++)
ans = Math.min(ans, dp[full - 1][i] + d[i][0]);
return ans;
}
public static void main(String[] args) {
int[][] a = {{0, 10, 15, 20}, {10, 0, 35, 25},
{15, 35, 0, 30}, {20, 25, 30, 0}};
int[][] b = {{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40},
{5, 30, 0, 25, 30}, {5, 25, 25, 0, 15},
{5, 40, 30, 15, 0}};
System.out.println(tsp(a));
}
}
Main.java:14: error: bad operand types for binary operator '&'
if (mask & 1 << j != 0) continue;
^
first type: int
second type: boolean
1 error
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Nearest neighbour | O(n²) | O(n) | fast but wrong |
| Every order | O(n!) | O(n) | 14 cities: Time Limit Exceeded |
| Bitmask DP (Held-Karp) | O(2ⁿ · n²) | O(2ⁿ · n) | 18 cities: ~100 ms |
For n = 20: about 4 × 10⁸ steps and 20 million table cells (80 MB as int), which is why problems stop around 20.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Nearest city first | 125 instead of 80 |
a short ride now forces a long one later | DP over (mask, city) |
| No ride home | 65 instead of 80 |
a path, not a tour | add d[i][0] at the end |
| No INF skip | -2147483629 |
Integer.MAX_VALUE + d overflows |
skip dp == INF (or use a smaller INF like 1e9) |
mask & 1 << j != 0 |
error: bad operand types for binary operator '&' |
!= binds tighter than & |
(mask & (1 << j)) != 0 |
| Start mask 0 instead of 1 | city 0 is "visited" twice | the start city is already in the set | dp[1][0] = 0 |
1 << n with n ≥ 31 |
overflow / negative size | an int has 32 bits |
keep n small (the DP is exponential anyway) |
Mini project: the rider's route card
Read the drop points as (x, y) coordinates, build the distance matrix with rounded Euclidean distances, run the DP with a parent table, and print the route in order with the distance of each leg. Compare it with nearest-neighbour on 10 random maps and count how often greedy is worse.
Practice
1. Shortest Path Visiting All Nodes (LeetCode 847). Unweighted graph, any start, nodes may repeat: breadth-first search over states (mask, node).
2. Find the Shortest Superstring (LeetCode 943). TSP where the "distance" from word i to word j is how many letters j adds after i.
3. Print the best tour, not just its length. Keep par[mask][j] = i and walk back from the best end city.
4. Count the masks for n = 4 by hand. 2⁴ = 16, from 0000 to 1111.
Solutions (1, 3 and 4)
import java.util.*;
public class Main {
// Shortest Path Visiting All Nodes (LeetCode 847): BFS over states (mask, node), start from every node.
static int shortestPathLength(int[][] graph) {
int n = graph.length, full = (1 << n) - 1;
boolean[][] seen = new boolean[1 << n][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) { q.add(new int[]{1 << i, i, 0}); seen[1 << i][i] = true; }
while (!q.isEmpty()) {
int[] s = q.poll();
if (s[0] == full) return s[2];
for (int j : graph[s[1]]) {
int next = s[0] | (1 << j);
if (!seen[next][j]) { seen[next][j] = true; q.add(new int[]{next, j, s[2] + 1}); }
}
}
return -1;
}
// Homework 3: print the best tour with a parent table.
static String tour(int[][] d) {
int n = d.length, full = 1 << n, INF = Integer.MAX_VALUE;
int[][] dp = new int[full][n], par = new int[full][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;
for (int mask = 1; mask < full; mask++)
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF) continue;
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
int next = mask | (1 << j);
if (dp[mask][i] + d[i][j] < dp[next][j]) { dp[next][j] = dp[mask][i] + d[i][j]; par[next][j] = i; }
}
}
int best = INF, end = 0;
for (int i = 1; i < n; i++)
if (dp[full - 1][i] + d[i][0] < best) { best = dp[full - 1][i] + d[i][0]; end = i; }
LinkedList<Integer> path = new LinkedList<>();
int mask = full - 1, city = end;
while (city != 0) { path.addFirst(city); int p = par[mask][city]; mask ^= 1 << city; city = p; }
path.addFirst(0);
path.addLast(0);
return best + " " + path;
}
public static void main(String[] args) {
System.out.println(shortestPathLength(new int[][]{{1, 2, 3}, {0}, {0}, {0}}));
System.out.println(shortestPathLength(new int[][]{{1}, {0, 2, 4}, {1, 3, 4}, {2}, {1, 2}}));
System.out.println(tour(new int[][]{{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}}));
System.out.println(tour(new int[][]{{0, 40, 5, 5, 5}, {40, 0, 30, 25, 40}, {5, 30, 0, 25, 30}, {5, 25, 25, 0, 15}, {5, 40, 30, 15, 0}}));
int count = 0;
for (int mask = 0; mask < 1 << 4; mask++) count++;
System.out.println("masks for n = 4: " + count);
}
}
4
4
80 [0, 2, 3, 1, 0]
80 [0, 4, 3, 1, 2, 0]
masks for n = 4: 16
Quick quiz
int mask = 13; (binary 1101). Which cities are in the set? A) {0, 2, 3} B) {1, 2, 3} C) {0, 1, 3} D) {1, 3, 4}
Answer
A) {0, 2, 3}. 13 = 8 + 4 + 1: bits 0, 2 and 3 are on; bit 1 is off.
Interview questions
- Why does nearest neighbour fail? It never looks ahead; a short ride now can force a long ride home.
- What is the state, and why is the order forgotten?
(visited set, current city): two partial tours with the same set and city have the same future. - How do you store a set in an int? Bit
j= cityj; test withmask & (1 << j), add withmask | (1 << j). - Why loop masks in increasing order? A transition only adds bits, so it always goes to a bigger mask.
- Complexity? O(2ⁿ · n²) time, O(2ⁿ · n) space; versus O(n!) for every order.
- How do you avoid overflow? Skip unreached states, or use an INF far below
Integer.MAX_VALUE(like 10⁹). - How do you print the tour? A parent table
par[mask][j], walked back from the best end city.
Glossary
| Term | Meaning |
|---|---|
| TSP | Visit every city once and return, as cheaply as possible |
| Tour | A round trip through every city |
| Nearest neighbour | Always go to the closest unvisited city |
| Backtracking | Mark, recurse, unmark |
| Bit | A single 0 or 1; bit j is worth 2^j |
| Bitmask | An int whose bits mark which items are in a set |
1 << j |
Only bit j set |
& / \| |
Bitwise AND (test a bit) / OR (set a bit) |
| Full mask | (1 << n) − 1: every item |
| State | (mask, city) |
| INF | "Not reached yet" |
| Overflow | An int past its maximum wraps to a negative value |
| Held-Karp | The bitmask DP for TSP |
Summary
- Nearest-first is wrong; every order is
O(n!). - Only
(visited set, current city)matters, and a set fits in the bits of an int. dp[mask][i], extended to eachjnot inmask; answermin dp[full][i] + d[i][0].- Skip unreached states (overflow!) and bracket every bit test.
- O(2ⁿ · n²) time, O(2ⁿ · n) space: fine up to about 20 cities.
- Next episode: bit manipulation: single number, counting bits and power of two.