https://www.acmicpc.net/problem/10974
initial
typical backtracking/permu questio nlike that n+m questions
solution
n = int(input())
lst = [i for i in range(1, n + 1)]
visited = [False for _ in range(n + 1)]
tmp = []
def dfs(tmp):
if len(tmp) == n:
print(*tmp)
return
for i in lst:
if not visited[i]:
tmp.append(i)
visited[i] = True
dfs(tmp)
tmp.pop()
visited[i] = False
dfs(tmp)revisited mar 4th 24
or if you pass the list and visited list as parameters of that dfs function, you dont need to undo the changes but i guess there isnt a way to mark that within the function like
dfs (tmp.append(i), visited[i]=True)
no such thing so my initial apporach is ideal. Just wanted to mention that passing as method parameters means that when you come back to the current scope after recurring, you have the unchanged variables.
complexity
For dfs time complexity, it all matters on the choice. If we had a graph question, time is normally v+ e cuz for every vertex, we visit each vertex v once and e edges once. But in this question, in the first loop we have n choices and the next loop we visit n-1 choices and next loop n-2 choices so this is basically n!.
For space it is n
