Traveling Salesman problem

'''
Start at city 0. From every city, try visiting all unvisited cities one by one — keep going deeper until all cities are visited.
At that point, return the cost of going back to city 0.

As the recursion unwinds, each call receives the "best cost from here onwards" from its children, adds its own travel cost,
and saves the best result for that (current_city, visited_set) state in memo — so if we ever land on the same city with the same visited set again,
we skip recomputing and directly return the saved answer.
'''
'''
Start at city 0. From every city, try visiting all unvisited cities one by one — keep going deeper until all cities are visited.
At that point, return the cost of going back to city 0.

As the recursion unwinds, each call receives the "best cost from here onwards" from its children, adds its own travel cost,
and saves the best result for that (current_city, visited_set) state in memo — so if we ever land on the same city with the same visited set again,
we skip recomputing and directly return the saved answer.

State is (city,(visited cities)) visited cities can be any subset of N ie. 2^N and city can be N so total N*2^N
each state we are doing sorting before pushing it into table or making a key, so visited can be max size=N so O(NlogN) for sorting for the key,then each state we are traversing O(N), then each state work= O(N+Nlog(N))=O(NLog(N)) as they are doing sequential.
for getting the next city to visit so O(N) total N^2*2^Nlog(N)

This can be improved by using the mask for visited cities in the dictionary 101101 kind of, which will reduce the everytime sorting overhead of log(N)
'''
def dfs(city, visited, cost, n, memo):
    if len(visited) == n:
        return cost[city][0]

    key = (city, tuple(sorted(visited))) #sorted is needed otherwise same key can be multiple keys if shuffled
    if key in memo:
        return memo[key]

    ans = float('inf')
    for nxt in range(n):
        if nxt not in visited:
            visited.add(nxt)
            ans = min(ans, cost[city][nxt] + dfs(nxt, visited, cost, n, memo))
            visited.remove(nxt)  # backtrack

    memo[key] = ans
    return ans

#Visited cities also stored int the dictionary or dp because we will avoid the already visited cities
class Solution:
    def tsp(self, cost):
        n = len(cost)
        memo = {} # (cur_city, {visited}): cur_city to next unvisited city cost+ min of all dfs routes
        visited = {0}
        ans=dfs(0, visited, cost, n, memo)
        return ans