005 Traveling Santa

It's Christmas, and Santa Claus is about to start delivering Christmas presents. He has a list of cities that he needs to visit, and Santa's elves have planned out the most efficient route that visits all cities exactly once, via their Traveling Santa Problem solver. However, just as Santa is about to leave, he spills hot chocolate on the itinerary, so the names of the cities are no longer readable. Fortunately, the distances between each destination are still visible. Given a list of distances between all cities, can you reconstruct the original itinerary? If there are several possible solutions, return all of them. Assume that Santa starts out from the North Pole.

Your challenge is to write a program that, given a list of distances between destinations, returns all possible itineraries that match the given distances.

The distances between the cities are:

North Pole - Helsinki: 10
North Pole - Oslo: 10
North Pole - Stockholm: 12
North Pole - Copenhagen: 14
North Pole - Berlin: 16
Helsinki - Stockholm: 4
Helsinki - Oslo: 8
Helsinki - Copenhagen: 9
Helsinki - Berlin: 11
Oslo - Stockholm: 4
Oslo - Copenhagen: 6
Oslo - Berlin: 9
Stockholm - Copenhagen: 5
Stockholm - Berlin: 8
Copenhagen - Berlin: 4

For example, given the distances 10, 4, 4, 6, 4 the solution is:

Helsinki, Stockholm, Oslo, Copenhagen, Berlin