TSP

O(x^2 2^x)

Towns already visited 2^x

Last town visited x

Next town to visit x

Some patterns return to the starting point and some do not.

code:python

def tsp_return(num_vertex, distances):

# ABC180E

INF = 9223372036854775807

SUBSETS = 2 ** num_vertex

for subset in range(1, SUBSETS):

for v in range(num_vertex):

for u in range(num_vertex):

mask = 1 << u

if subset & mask:

def tsp_not_return(num_vertex, distances, from_start):

# PAST3M

INF = 9223372036854775807

SUBSETS = 2 ** num_vertex

for subset in range(1, SUBSETS):

for v in range(num_vertex): # new vertex

mask = 1 << v

if subset == 1 << v:

# previous vertex is start

elif subset & mask: # new subset includes v

for u in range(num_vertex):

---