I am having trouble coming up with the space complexity of the TSP algorithm.
https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
To me the space complexity for the brute force is the cost of storing all possible permutations right ? That should take space O($N!$) where N is the number of cities/nodes/vertexes.
Similarly for the Dynamic Programming algorithm it stores all tours, that is also O($N!$), but the site says the space complexity is O($2^{N}$)
Can someone explain if my logic for space complexities is correct, especially for the Dynamic Programming algorithm.
Thank you