Travelling Salesman (Held-Karp)

Difficulty: Hard · Topic: Dynamic programming

Given an n × n distance matrix dist (dist[i][j] = distance from city i to j), return the length of the shortest tour that starts at city 0, visits every city exactly once, and returns to 0.

Use Held-Karp: dp[mask][i] = the cheapest path that starts at 0, visits exactly the set mask, and ends at i. It's exponential (O(2ⁿ·n²)) — TSP is NP-hard — but exact for small n.

Examples

held_karp([[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]])
→ 80

0→1→3→2→0 = 10+25+30+15.

held_karp([[0,1],[1,0]])
→ 2

Target complexity: time O(2ⁿ · n²), space O(2ⁿ · n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.