Log inSign up
hardLeetCodeNot Started

Travelling Salesman Problem

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

Given a complete undirected weighted graph represented as an n x n cost matrix cost, where cost[i][j] is the cost of travelling from city i to city j.

Find the minimum cost of a Hamiltonian tour: visit every city exactly once and return to the starting city (city 0).

Constraints:

  • 1 <= n <= 16
  • cost[i][j] == cost[j][i]
  • cost[i][i] == 0
  • 1 <= cost[i][j] <= 104 for i != j

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the Travelling Salesman Problem (TSP) and Hamiltonian tour concept.
  • Model subsets of visited vertices compactly using integer bitmasks.
  • Formulate the Held-Karp recurrence: DP(mask, u).
  • Analyze time complexity improvement from O(N!) to O(N2 \cdot 2N).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a problem requires visiting all N vertices in a graph with minimum cost or shortest path and N <= 16 to 20, think of Bitmask DP (Held-Karp pattern).

1. Permutation Backtracking

Intuition

Fix the starting city at 0. Generate all (N - 1)! permutations of the remaining cities 1 \dots N - 1. For each permutation, calculate the cost of traversing the sequence and returning to city 0. Find the minimum cost among all permutations.

Algorithm

  1. Initialize minCost = infinity.
  2. Create an array of cities [1, 2, ..., n - 1].
  3. Generate all permutations of these cities.
  4. For each permutation [c1, c2, ..., cn-1]:
  5. total = cost[0][c1] + cost[c1][c2] + ... + cost[cn-1][0]
  6. minCost = min(minCost, total)
  7. Return minCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5#include <climits>
6
7int tspBrute(int n, const std::vector<std::vector<int>>& cost) {
8 std::vector<int> cities;
9 for (int i = 1; i < n; ++i) cities.push_back(i);
10
11 int minCost = INT_MAX;
12 do {
13 int currentCost = cost[0][cities[0]];
14 for (int i = 0; i < (int)cities.size() - 1; ++i) {
15 currentCost += cost[cities[i]][cities[i + 1]];
16 }
17 currentCost += cost[cities.back()][0];
18 minCost = std::min(minCost, currentCost);
19 } while (std::next_permutation(cities.begin(), cities.end()));
20
21 return minCost;
22}
23
24int main() {
25 int n = 3;
26 std::vector<std::vector<int>> cost = {{0, 10, 15}, {10, 0, 20}, {15, 20, 0}};
27 std::cout << "TSP (Brute Force): " << tspBrute(n, cost) << std::endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N!) because there are (N - 1)! permutations, each evaluated in O(N) time.
  • Space complexity: O(N) for recursion stack and permutation storage.

2. Branch and Bound with Pruning

Intuition

Instead of enumerating all permutations blindly, prune any search branch whose current accumulated cost plus an admissible lower bound on the remaining path exceeds the best total tour cost found so far.

Algorithm

  1. Initialize bestCost = infinity.
  2. Track visited boolean array.
  3. Compute minimum outgoing edge for each city as a simple bounding heuristic.
  4. Run recursive backtracking search(currCity, count, currentCost):
  5. If currentCost >= bestCost, prune branch.
  6. If count == n:
  7. bestCost = min(bestCost, currentCost + cost[currCity][0])
  8. return.
  9. For each unvisited city v:
  10. search(v, count + 1, currentCost + cost[currCity][v])
  11. Return bestCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6void branchAndBound(int curr, int count, int currentCost, int n, const std::vector<std::vector<int>>& cost,
7 std::vector<bool>& visited, int& bestCost) {
8 if (currentCost >= bestCost) return;
9 if (count == n) {
10 bestCost = std::min(bestCost, currentCost + cost[curr][0]);
11 return;
12 }
13
14 for (int next = 0; next < n; ++next) {
15 if (!visited[next]) {
16 visited[next] = true;
17 branchAndBound(next, count + 1, currentCost + cost[curr][next], n, cost, visited, bestCost);
18 visited[next] = false;
19 }
20 }
21}
22
23int tspBranchAndBound(int n, const std::vector<std::vector<int>>& cost) {
24 std::vector<bool> visited(n, false);
25 visited[0] = true;
26 int bestCost = INT_MAX;
27 branchAndBound(0, 1, 0, n, cost, visited, bestCost);
28 return bestCost;
29}
30
31int main() {
32 int n = 3;
33 std::vector<std::vector<int>> cost = {{0, 10, 15}, {10, 0, 20}, {15, 20, 0}};
34 std::cout << "TSP (Branch and Bound): " << tspBranchAndBound(n, cost) << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N!) worst case, but significantly faster on average due to bound pruning.
  • Space complexity: O(N) for recursion stack.

3. Held-Karp Dynamic Programming with Bitmask

Intuition

Notice optimal substructure: to find the minimum cost to complete the tour given a subset of already visited cities and current city u, we only care about mask (the set of visited cities) and u (the current endpoint), not the order in which those cities were visited! We memoize dp[mask][curr], reducing the exponential states to (2N × N).

Algorithm

  1. Initialize 2D memo table memo[1 << n][n] with -1.
  2. Define tsp(mask, u):
  3. If mask == (1 << n) - 1 (all cities visited):
  4. Return cost[u][0] (return trip to city 0).
  5. If memo[mask][u] != -1, return memo[mask][u].
  6. ans = infinity
  7. For each city next from 0 to n - 1:
  8. If !(mask & (1 << next)) (not yet visited):
  9. candidate = cost[u][next] + tsp(mask | (1 << next), next)
  10. ans = min(ans, candidate)
  11. Return memo[mask][u] = ans.
  12. Return tsp(1, 0) (mask 1 = only city 0 visited).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6int solveTSP(int mask, int u, int n, const std::vector<std::vector<int>>& cost, std::vector<std::vector<int>>& memo) {
7 if (mask == (1 << n) - 1) {
8 return cost[u][0]; // Return to starting city 0
9 }
10 if (memo[mask][u] != -1) return memo[mask][u];
11
12 int ans = INT_MAX;
13 for (int next = 0; next < n; ++next) {
14 if (!(mask & (1 << next))) {
15 int subCost = solveTSP(mask | (1 << next), next, n, cost, memo);
16 if (subCost != INT_MAX) {
17 ans = std::min(ans, cost[u][next] + subCost);
18 }
19 }
20 }
21 return memo[mask][u] = ans;
22}
23
24int tspHeldKarp(int n, const std::vector<std::vector<int>>& cost) {
25 std::vector<std::vector<int>> memo(1 << n, std::vector<int>(n, -1));
26 return solveTSP(1, 0, n, cost, memo);
27}
28
29int main() {
30 int n = 3;
31 std::vector<std::vector<int>> cost = {{0, 10, 15}, {10, 0, 20}, {15, 20, 0}};
32 std::cout << "Optimal TSP (Held-Karp): " << tspHeldKarp(n, cost) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N^2 * 2^N) because there are N * 2^N states, and each state transitions to up to N other cities.
  • Space complexity: O(N * 2^N) for the DP memoization table.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Permutation BacktrackingO(N!)O(N)Simple factorial enumeration.Completely impractical for N > 10.
2.Branch and BoundO(N!) worst caseO(N)Prunes hopeless branches using bounds; good for medium N with structured weights.Worst-case remains factorial.
3.Held-Karp DP with BitmaskOptimalO(N^2 * 2^N)O(N * 2^N)Optimal exact algorithm for TSP; runs in seconds for N up to 16-20.Exponential space and time limits applicability beyond N ~ 22.

Common Pitfalls & Crucial Edge Cases

Forgetting to add the return edge cost[curr][0] at the end of the tour.

TSP is a closed tour (Hamiltonian cycle), not an open Hamiltonian path. The cost must include returning to the initial city.

Sizing the memo table as [1 << n][1 << n] instead of [1 << n][n].

The second dimension is the current city index u, which ranges from 0 to n - 1, not 2n.

Crucial Edge Cases to Validate:

  • n = 1 — Cost to visit city 0 and return is cost[0][0] = 0.
  • n = 2 — Only one possible tour: 0 -> 1 -> 0, cost is cost[0][1] + cost[1][0].
  • Symmetric cost matrix vs asymmetric cost matrix — Held-Karp works identically for both symmetric and asymmetric TSP cost matrices.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the problem complexity immediately: 'TSP is NP-hard. For N <= 16-20, the exact optimal approach is Held-Karp DP with Bitmask running in O(N2 * 2N).'
  2. Explain the state representation: mask represents the subset of visited vertices, u represents the current city.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can the starting city be arbitrarily fixed at city 0 without loss of generality?

2.What is the time complexity reduction achieved by Held-Karp over brute-force permutation?

3.What does the base case mask == (1 << n) - 1 signify?

Back to DSA Sheet