Here's the full solution:
plaintext function tsp(cost, n) INF := large number dp := 2D (two-dimensional) array [2^n][n], filled with INF dp[1][0] := 0 // start at city 0 for mask := 1 to 2^n - 1 for last := 0 to n - 1 if dp[mask][last] = INF then continue if (mask >> last) & 1 = 0 then continue for next := 0 to n - 1 if (mask >> next) & 1 = 1 then continue newMask := mask | (1 << next) dp[newMask][next] := min(dp[newMask][next], dp[mask][last] + cost[last][next]) ans := INF for last := 0 to n - 1 ans := min(ans, dp[2^n - 1][last] + cost[last][0]) return ans if ans < INF else "IMPOSSIBLE"
Time: . Space: . For , this runs in a few seconds.
Time: . Space: .