390. Travelling Salesman Problem

Given n cities (0-indexed) and an n x n cost matrix (cost[i][j] is the cost to travel directly from city i to city j), starting and ending at city 0, find the minimum total cost of a tour that visits every other city exactly once.

Input: The first line contains n, the number of cities. Each of the next n lines contains n space-separated integers, the cost matrix. Output: Print a single integer - the minimum total cost of a tour starting and ending at city 0 that visits every other city exactly once.

1 <= n <= 15

This bitmask DP is the standard 'exact' solution approach for TSP at small scale (n<=15-20) - for LARGER instances, this exact approach becomes infeasible, and real-world TSP solvers switch to approximation algorithms or heuristics instead.

Find the minimum cost of a tour visiting every city exactly once, starting and ending at the same city. Brute force: Try every possible PERMUTATION of the other n-1 cities as the visiting order - this costs O(n!), completely impractical beyond very small n (though the given constraint n<=15 pushes toward the DP approach specifically to handle up to that size). Optimised: The bitmask DP technique recognizes that the OPTIMAL cost to complete a tour only depends on WHICH SET of cities has been visited so far and WHERE you currently are - not the SPECIFIC ORDER used to visit them - collapsing the n! possible orderings down to just (2^n * n) distinct (mask, city) states, each computed once.

Define dp[mask][i] as the minimum cost to start at city 0, visit exactly the set of cities in mask, and end at city i. Base case dp[{0}][0] = 0. Transition: dp[mask][i] = min over every j in mask (other than i) of dp[mask without i][j] + cost[j][i]. The answer is the minimum over all i of dp[full mask][i] + cost[i][0]. Because there are only 2^n subsets and n choices of ending city, this reuses overlapping work across permutations that share the same visited set, turning a factorial search into one that is exponential only in n, which is dramatically smaller for n up to 15. Time: O(n^2 * 2^n) Space: O(n * 2^n)

Build tours incrementally city by city using recursive backtracking, but at each step prune any partial tour whose accumulated cost has already reached or exceeded the best complete tour cost found so far, abandoning that branch immediately instead of continuing to explore it. This still has the same O(n!) worst case as trying every permutation, but in practice it discards huge portions of the search space early, since most partial paths become provably suboptimal well before completion. Time: O(n!) Space: O(n)

Generate every permutation of the n - 1 non-starting cities, and for each permutation compute the total cost of the tour that starts at city 0, visits the cities in that order, and returns to city 0, keeping the minimum cost found. This tries every possible tour and is guaranteed correct, but the number of permutations grows factorially, making it usable only for very small n. Time: O(n!) Space: O(n)

1. Use BITMASK DP: state (mask, u) = the minimum cost to have visited exactly the set of cities in `mask`, currently sitting at city u, having started at city 0. 2. Transition from (mask, u) by trying every city v NOT yet in mask: cost(mask | (1<<v), v) = min(current value, cost(mask, u) + cost[u][v]). 3. The answer is the minimum, over every city u != 0, of (cost of visiting all cities ending at u) + cost[u][0] (the trip back to the start).

Time: O(n² * 2^n) - for each of the 2^n possible masks and n possible current cities, trying n possible next cities. Space: O(n * 2^n), for the DP table indexed by (mask, current city).

Test n = 1 (only city 0, tour cost 0) and n at its upper bound of 15, which is the largest the bitmask DP's 2^n states can handle.

Be ready to explain clearly WHY the state only needs (mask, current city) and not the full visiting order - this dramatic state-space reduction (from factorial to exponential-but-much-smaller) is exactly what makes TSP solvable exactly for n up to around 15-20, though it remains NP-hard for larger n.