LeetCode 46. 全排列（回溯算法入门模板）

LeetCode 46. 全排列回溯算法入门模板一、题目描述给定一个没有重复数字的数组nums返回它的所有可能全排列。示例输入nums[1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]二、看到题目先想到什么题目要求把数组里的数字全部用上每个数字只能使用一次求所有可能情况。这种「求所有可能」的问题通常都可以往**回溯算法Backtracking**上想。回溯算法本质上就是尝试一种选择 → 继续往下走 → 走不通或者走到底后撤销选择 → 再尝试下一种选择。有点像走迷宫走一步 ↓ 还能走 ↓ 继续走 ↓ 走到底 ↓ 退回来 ↓ 换条路继续走三、核心思想深度优先搜索DFS例如nums[1,2,3]第一位可以选1 2 3如果第一位选了11 ├──2 │ └──3 └──3 └──2如果第一位选了22 ├──1 │ └──3 └──3 └──1如果第一位选了33 ├──1 │ └──2 └──2 └──1最终得到123 132 213 231 312 321四、回溯算法三大核心变量1、res保存最终结果。res[]2、path当前正在构造的排列。例如[1][1,2][1,2,3]path[]3、used记录数字是否已经被使用。used[False]*len(nums)例如nums[1,2,3]used[True,False,True]表示1 已使用 2 未使用 3 已使用五、回溯的固定模板defbacktrack():if满足结束条件:保存结果returnfor选择列表:做选择 backtrack()撤销选择这四步必须记住做选择 递归 撤销选择 继续下一种选择六、代入本题第一步选择一个数字例如path[]选择1变成path[1]并且used[0]True第二步递归继续选择下一个数字。例如path[1]可以选择2 3第三步走到底得到path[1,2,3]长度已经等于len(nums)说明生成了一个完整排列。保存res.append(path[:])第四步回溯退回来path.pop()used[i]False继续尝试其他数字。七、完整代码fromtypingimportListclassSolution:defpermute(self,nums:List[int])-List[List[int]]:res[]path[]used[False]*len(nums)defbacktrack():# 终止条件iflen(path)len(nums):res.append(path[:])return# 枚举所有数字foriinrange(len(nums)):# 已经使用过ifused[i]:continue# 做选择used[i]Truepath.append(nums[i])# 递归backtrack()# 撤销选择path.pop()used[i]Falsebacktrack()returnres八、执行过程演示以nums[1,2,3]为例[] │ ├──1 │ ├──2 │ │ └──3 │ └──3 │ └──2 │ ├──2 │ ├──1 │ │ └──3 │ └──3 │ └──1 │ └──3 ├──1 │ └──2 └──2 └──1最终[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]九、为什么要存副本很多同学会这样写res.append(path)这是错误的。因为path是一个列表对象。后面回溯时path.pop()会修改原来的列表。最终结果可能变成[[],[],[],[],[],[]]或者[[3,2,1],[3,2,1],[3,2,1]]正确写法res.append(path[:])或者res.append(list(path))十、高频易错点1、忘记回溯错误path.append(nums[i])backtrack()少了path.pop()会导致路径越来越长。2、忘记恢复状态错误used[i]Truebacktrack()少了used[i]False后面的数字无法再次使用。3、保存结果没用副本错误res.append(path)正确res.append(path[:])4、终止条件写错正确iflen(path)len(nums):因为只有路径长度等于数组长度时才生成一个完整排列。十一、复杂度分析时间复杂度O(n × n!)原因一共有n!个排列每个排列保存时需要复制n个元素。空间复杂度O(n)主要来自递归栈pathused数组。结果数组不算额外空间。十二、回溯题万能模板res[]path[]defbacktrack():if满足结束条件:res.append(path[:])returnfor选择列表:if当前选择不合法:continue# 做选择path.append(选择)# 递归backtrack()# 撤销选择path.pop()十三、一句话总结回溯算法的核心就是做选择 → 递归 → 撤销选择。全排列题目的本质枚举每一个位置能放什么数字走到底得到一种排列然后回退继续尝试其他可能。掌握这道题之后后面的组合77子集78组合总和39N 皇后51都会发现是同一个回溯模板的变形。