A set of visited stops fits in one number
When the state is which items you have used, a row of yes/no switches packs that set into a single number. About 16 minutes.
Visit every stop and come home
You start at stop 0 and must visit every other stop exactly once, then return home. You know the distance between each pair of stops, and you want the shortest total trip. With n stops there are n minus 1 factorial orders, which is hopeless beyond about ten stops.
The key insight is that, to decide what to do next, you only need to know two things about the trip so far: which stops you have visited, and where you are now. How you got there no longer matters.
Grow the set one stop at a time
Keep the cheapest cost for every pair of a visited set and a current stop. Start with the sets of one stop, straight from home. Then grow: from a set and a stop, step to an unvisited stop, add the distance, and record it for the bigger set if it is cheaper than what is there.
When every stop is visited, add the way home from each last stop, and take the cheapest. To check whether a stop is in the set, test its bit, and to add it, switch its bit on.
full = (1 << n) - 1 # every stop visited
Start from home. Going straight to place 1 costs 10, to place 2 costs 15, to place 3 costs 20. Each is a set of one place.
To end at place 2 having visited {1, 2, 3}, which earlier state could you have come from?
- AVisited {1, 3}, standing at 1 or at 3
- BVisited {1, 2, 3}, standing at 2
- CVisited {2}, standing at 2
Show the answer
Visited {1, 3}, standing at 1 or at 3. One step adds exactly one place, and place 2 is the one being added.
Shortest round trip
There are n places, numbered 0 to n − 1, and dist[i][j] is the distance from place i to place j (the same in both directions). Starting at place 0, visit every other place exactly once and return to place 0. Return the smallest possible total distance.
dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] → 80
1 ≤ n ≤ 12 · 1 ≤ dist[i][j] ≤ 100 for i ≠ j · dist[i][i] = 0