回溯——全排列（python）

思路：DFS深度遍历到最底层，到递归最底层时，收集答案，然后回溯到上一层，再搜索没有访问的节点。

注意：使用visit数组，标记访问过的数字。递归之后记得回溯

from typing import List def permute(n)->List[List[int]]: res=[] visit=[0]*n path=[] nums=[] for i in range(n): #先创建数组 nums.append(i+1) def dfs(pos): nonlocal res,path,visit if pos==n: #到达最后一个位置，收集答案 res.append(path[:]) return for i in range(n): if visit[i]==0: #表示该数字还未访问 path.append(nums[i]) visit[i]=1 dfs(pos+1) #继续递归填下一个位置 path.pop() #回溯 visit[i]=0 dfs(0) #准备去填第0个空位 print(res) return res def main(): n=int(input()) permute(n) if __name__=="__main__": main()