What Is the Traveling Salesman Problem? Every City Once, No Easy Answer
- Traveling Salesman Problem asks for the shortest Hamiltonian cycle through all cities — simple to state, NP-hard to solve optimally
- Brute force is O(n!): at 20 cities, exhaustive search takes ~4 years at 1 billion routes per second
- Held-Karp DP reduces the search to O(n²·2^n) using bitmask states — exact but still exponential, practical only up to about 20 cities
- TSP is NP-hard: a polynomial-time solution would prove P = NP; Christofides gives the best known 3/2 approximation for metric TSP
- The key interview signal: n ≤ 20 combined with "visit all nodes" or "minimum cost covering every element" means bitmask DP
- LeetCode 847 (Shortest Path Visiting All Nodes) and 943 (Find the Shortest Superstring) are the canonical bitmask DP interview problems with the same TSP structure
You have a salesman. He needs to visit five cities and return home. Simple enough. Now make it optimal, visiting each city exactly once, finding the shortest possible route. How hard can that be?
Hard enough that no one has found a fast general solution in over 70 years. The question of whether one exists is one of the most famous unsolved problems in computer science. Your salesman is not going home anytime soon.
Simple to State, Impossible to Solve Exactly
The Traveling Salesman Problem (TSP) takes a set of cities and the distances between every pair, then asks: what is the shortest route that visits each city exactly once and returns to the starting city?
That cycle, visiting every node exactly once and returning to the start, is called a Hamiltonian cycle. TSP is the optimization version: not just "does one exist?" but "which one is shortest?"
The problem sounds simple because the individual pieces are simple. Distances are just numbers. A valid route is just an ordering. But the number of orderings explodes so fast that brute force becomes physically impossible at surprisingly small inputs. And "physically impossible" is doing real work in that sentence.
Four Cities, Six Routes
Say you have cities A, B, C, and D. Distances between every pair:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 10 | 15 | 20 |
| B | 10 | 0 | 35 | 25 |
| C | 15 | 35 | 0 | 30 |
| D | 20 | 25 | 30 | 0 |
You start at A and must return to A. How many routes exist?
Fix the starting city (A), then count orderings of the remaining three. That's 3! = 6 routes:
| Route | Cost |
|---|---|
| A → B → C → D → A | 10 + 35 + 30 + 20 = 95 |
| A → B → D → C → A | 10 + 25 + 30 + 15 = 80 |
| A → C → B → D → A | 15 + 35 + 25 + 20 = 95 |
| A → C → D → B → A | 15 + 30 + 25 + 10 = 80 |
| A → D → B → C → A | 20 + 25 + 35 + 15 = 95 |
| A → D → C → B → A | 20 + 30 + 35 + 10 = 95 |
Optimal cost: 80, via A → B → D → C → A (or its reverse).
Six routes is manageable. You could enumerate them by hand over lunch. Now watch what happens when the city count grows.
The Number of Routes Is Cosmically Stupid
With n cities, you fix the start, then permute the remaining n - 1. The number of routes is (n - 1)!.
| Cities | Routes |
|---|---|
| 5 | 24 |
| 10 | 362,880 |
| 15 | 87 billion |
| 20 | 122 quadrillion |
| 25 | 620 sextillion |
At 20 cities, checking every route at one billion routes per second takes roughly four years. At 25, it's 20 million years. A laptop solves n = 10 in milliseconds and grinds to a halt around n = 15. The same laptop that renders video and runs a browser with 47 tabs.
This exponential collapse is not a coding problem. There's no clever data structure that fixes it. It's a fundamental property of the search space, and the search space does not care about your feelings.
Proposing brute force on 25 TSP cities. The universe is the interviewer.
How DP Helps (and Where It Stops Helping)
In 1962, Richard Bellman, Michael Held, and Richard Karp independently found a dynamic programming approach to the traveling salesman problem that dramatically improves on brute force. Three people, same year, same idea. At least they all agreed on something.
The insight: instead of recomputing subpaths you've already solved, cache them.
The state is dp[mask][i], the minimum cost to visit exactly the cities encoded in mask, ending at city i. A bitmask is a compact integer where bit k is set if city k has been visited, letting you represent any subset of n cities in a single integer.
def tsp(dist): n = len(dist) INF = float('inf') # dp[mask][i] = min cost to reach city i, having visited cities in mask dp = [[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 u in range(n): if dp[mask][u] == INF: continue if not (mask >> u & 1): continue for v in range(n): if mask >> v & 1: continue next_mask = mask | (1 << v) new_cost = dp[mask][u] + dist[u][v] dp[next_mask][v] = min(dp[next_mask][v], new_cost) full = (1 << n) - 1 return min(dp[full][i] + dist[i][0] for i in range(n))
Three nested loops: O(n²·2^n) time, O(n·2^n) space.
Let's trace the four-city example. Start: dp[0001][0] = 0 (at A, cost 0, only A visited).
Extend to B: dp[0011][1] = 10. To C: dp[0101][2] = 15. To D: dp[1001][3] = 20.
From B, go to D: dp[1011][3] = 10 + 25 = 35. From B, go to C: dp[0111][2] = 10 + 35 = 45.
Keep filling until dp[1111][i] is complete for every possible end city. The answer is min(dp[1111][i] + dist[i][0]). Path ending at C via A→B→D→C: 35 + 30 = 65. Add the return leg: 65 + 15 = 80. Correct.
The Held-Karp algorithm is the best exact algorithm known. It reduces O(n!) to O(n²·2^n). At n = 20, that's 400 million operations instead of 60 quadrillion. Still exponential, but at least a solvable kind of exponential.
Why Nobody Has Solved TSP Exactly (and Won a Million Dollars)
TSP is NP-hard. This is a precise claim, not a synonym for "very difficult."
The proof works by reduction from Hamiltonian cycle, which is NP-complete. If you could solve TSP in polynomial time, you could also solve Hamiltonian cycle in polynomial time. Since that's NP-complete, polynomial TSP would prove P = NP, which most computer scientists believe is false and also worth a million dollars in Clay Millennium Prize money.
No polynomial-time exact algorithm is known. Finding one (or proving none exists) would resolve the P vs NP problem, the most consequential open question in theoretical computer science. So if you crack TSP on a flight home, don't close the laptop.
So what do practitioners do?
Approximation algorithms. For metric TSP (where distances satisfy the triangle inequality), the Christofides-Serdyuk algorithm from 1976 guarantees a tour within 3/2 of optimal. In 2020, Karlin, Klein, and Gharan broke that 44-year ceiling with an approximation of 3/2 minus a tiny positive constant. After 44 years, someone squeezed out an epsilon. Progress.
Heuristics. The nearest-neighbor heuristic greedily picks the closest unvisited city at each step. Fast, often decent, arbitrarily bad on adversarial inputs. The kind of thing that works great until it doesn't.
Modern solvers. Tools like Concorde TSP Solver combine branch-and-bound, linear programming relaxations, and cutting planes. They routinely find optimal solutions for instances with thousands of cities. Worst-case behavior is still exponential. The universe has limits.
The Pattern That Actually Shows Up in Interviews
You will almost never see "solve TSP exactly" in a standard interview. Too open-ended, too academic for 45 minutes.
What you will see is the bitmask DP pattern that Held-Karp uses.
Any problem asking you to visit a small set of nodes in some optimal order is likely bitmask DP. The constraint to watch for: n ≤ 20, combined with "visit all nodes" or "minimum cost to cover every element." The bitmask encodes state compactly enough to make the DP tractable. When you see that constraint pair, your brain should say "bitmask DP" before you finish reading the problem.
LeetCode 847, "Shortest Path Visiting All Nodes," is the canonical example. You're given an undirected graph and need the shortest path visiting every node. The state is (current_node, visited_bitmask). Same structure as TSP, without the full combinatorial hardness.
LeetCode 943, "Find the Shortest Superstring," applies the same pattern: find the shortest string containing each word as a substring. Model it as TSP on strings, track which strings you've included in your bitmask.
The algorithm template is the same each time:
- State: current node and a bitmask of visited nodes.
- Transition: extend to any unvisited node.
- Base case: only the starting node is visited.
- Answer: close the tour when all bits are set.
The hard part is recognizing the structure. Once you see it, the implementation follows directly. That recognition gap, knowing that "visit all nodes optimally with n ≤ 20" means bitmask DP, is exactly what an interview is testing.
For live practice on bitmask DP under time pressure, SpaceComplexity runs voice-based mock interviews with real feedback. Pattern recognition at a desk is one skill. Pattern recognition when a timer is running and someone is watching is another.
Further Reading
- Travelling Salesman Problem (Wikipedia): full problem history, variants, and complexity theory
- Held-Karp Algorithm (Wikipedia): the exact DP formulation with full proofs
- Christofides Algorithm (Wikipedia): the 3/2 approximation for metric TSP
- GeeksforGeeks: Travelling Salesman Problem using DP: step-by-step Held-Karp walkthrough
- LeetCode 847: Shortest Path Visiting All Nodes: the bitmask DP pattern in a solvable interview problem