AlgoNote 算法通关手册：LeetCode 0046「全排列」回溯算法深度解析

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载全排列Permutations是回溯算法最经典的入门问题也是算法面试中高频出现的「排列、组合、子集」三类问题的起点。本篇基于 AlgoNote 算法通关手册的题解文档结合手册中回溯算法专题的系统讲解带你从决策树建模、回溯函数设计到代码实现完整走一遍「选择 - 递归 - 回溯」的标准流程并延伸到含重复元素的全排列 II 去重技巧读完即可独立秒杀同类型的排列类问题。题目概览题目描述给定一个不含重复数字的数组nums返回其所有可能的全排列。题目要求返回数组nums的所有全排列顺序不限。数据范围说明$1 \le nums.length \le 6$$-10 \le nums[i] \le 10$nums中的所有整数互不相同正因为无重复元素才可以直接用「当前路径中是否已包含该元素」来判断能否选择示例示例 1输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2输入nums [0,1] 输出[[0,1],[1,0]]该题在手册中归属于回溯算法题目标签为「数组、回溯」难度为中等。回溯算法的核心思想在动手写代码之前先理解回溯算法本身。AlgoNote 手册在回溯算法简介中给出定义回溯算法Backtracking一种系统地搜索所有可能解的算法通过递归和试错的方式逐步构建解。当发现当前路径无法满足题目要求或无法得到有效解时撤销上一步的选择即「回溯」返回到上一个决策点尝试其他可能的路径。核心思想是「走不通就退回换条路再试」每次需要回退的节点称为「回溯点」。简而言之回溯算法就是「遇到死路就回头」其实现要点是选择元素从当前可选的数字中挑选一个未被使用的数字加入路径递归探索递归进入下一层继续选择下一个位置的数字直到满足终止条件撤销选择回溯递归返回后移除刚才选择的数字恢复现场尝试其他分支直到所有可能路径都被遍历。回溯过程通常有两种结果要么找到一个满足条件的解要么尝试所有可能后确认无解。全排列问题属于前者——解空间就是所有排列回溯会穷尽地枚举出每一个。解题思路回溯算法三步走第一步明确所有选择画出决策树全排列中每个位置上的元素都可以从「剩余可选元素」中选出。以nums [1, 2, 3]为例决策树的结构是第 1 层第一个位置可选1、2、3三个分支第 2 层在已选一个数字后第二个位置从剩余两个数字中选第 3 层最后的位置只剩一个数字可选形成叶子节点。决策树与回溯的对应关系依据回溯算法基础篇的归纳每一层代表当前递归的深度每个节点及其分支对应一次不同的选择每个节点表示当前排列的一个「状态」即已选择的数字序列向下递归一层相当于在可选数字中再选一个加入当前状态当某条分支探索结束后递归逐层回退回溯撤销最近的选择恢复到上一个状态继续尝试其他分支。第二步明确终止条件当遍历到决策树的叶子节点时递归终止。对应到代码中就是当前路径path的长度等于给定数组nums的长度即len(path) len(nums)说明此时已经选完了所有位置构成一个完整排列。第三步将决策树和终止条件翻译成代码1. 定义回溯函数backtracking(nums)传入参数是nums可选数组列表全局变量是res存放所有符合条件结果的集合数组和path存放当前符合条件的结果函数含义递归在nums中选择剩下的元素。2. 书写回溯函数主体选择、递归搜索、撤销选择从当前正在考虑的元素开始到数组结束为止枚举所有可选的元素。对于每一个可选元素约束条件之前已经选择的元素不再重复选用只能从剩余元素中选择选择元素将其添加到当前路径数组path中递归搜索在选择该元素的情况下继续递归选择剩下的元素撤销选择将该元素从当前结果数组path中移除。for i in range(len(nums)): # 枚举可选元素列表 if nums[i] not in path: # 从当前路径中没有出现的数字中选择 path.append(nums[i]) # 选择元素 backtracking(nums) # 递归搜索 path.pop() # 撤销选择3. 明确递归终止条件及处理方法当len(path) len(nums)时说明找到了一组完整排列将path的副本加入res然后return结束当前分支。完整代码与逐行解析以下是题解文档给出的标准回溯实现class Solution: def permute(self, nums: List[int]) - List[List[int]]: res [] # 存放所有符合条件结果的集合 path [] # 存放当前符合条件的结果 def backtracking(nums): # nums 为选择元素列表 if len(path) len(nums): # 说明找到了一组符合条件的结果 res.append(path[:]) # 将当前符合条件的结果放入集合中 return for i in range(len(nums)): # 枚举可选元素列表 if nums[i] not in path: # 从当前路径中没有出现的数字中选择 path.append(nums[i]) # 选择元素 backtracking(nums) # 递归搜索 path.pop() # 撤销选择 backtracking(nums) return res逐行拆解关键点res.append(path[:])必须拷贝一份path再放入结果。因为path是共享的可变列表后续递归回溯时会不断pop()如果直接append(path)最终res里存的全是同一个被清空的列表对象。path[:]生成浅拷贝保存当前状态的快照。这一细节在手册的回溯通用模板中也特别强调「注意要拷贝一份 path避免后续修改影响结果」。nums[i] not in path利用「元素互不相同」的前提条件用列表in判断来模拟「该数字是否已被选用」。这相当于一种约束剪枝保证同一排列中每个数字只出现一次。递归调用backtracking(nums)不携带path参数因为path作为闭包内的全局变量在递归各层共享天然表达了「当前状态」。path.pop()是回溯的关键动作撤销本轮选择恢复上一层状态从而可以继续尝试其他分支。以nums [1, 2, 3]为例回溯的执行轨迹为先选1再选2再选3得到[1,2,3]回退撤销3、2改选3得到[1,3,2]再回退撤销1改以2开头……最终穷尽全部 6 种排列。回溯算法的通用模板从全排列的实现中可以提炼出手册中总结的回溯算法通用模板适用于排列、组合、子集等绝大多数枚举类问题res [] # 存放所有符合条件结果的集合 path [] # 存放当前递归路径下的结果 def backtracking(nums): # 递归终止条件根据具体问题设定如 path 满足特定条件 if 满足结束条件: # 例如len(path) len(nums) res.append(path[:]) # 拷贝一份 path避免后续修改影响结果 return # 遍历所有可选的元素 for i in range(len(nums)): # 可选根据具体问题添加剪枝条件如元素不能重复选取 # if nums[i] in path: # continue path.append(nums[i]) # 做选择将当前元素加入 path backtracking(nums) # 递归继续选择下一个元素 path.pop() # 撤销选择回退到上一步状态 backtracking(nums)回溯算法的标准流程可以概括为「先枚举所有可选项再判断是否满足终止条件最后递归深入并在必要时撤销选择」。在手册中回溯的代码骨架被归纳为def backtrack(参数): if 终止条件: 处理结果 return for 选择 in 可选列表: if 满足约束: 做选择 backtrack(新参数) 撤销选择复杂度分析时间复杂度$O(n \times n!)$其中 $n$ 为数组nums的元素个数。$n$ 个元素的全排列共有 $n!$ 种每生成一个排列需要 $O(n)$ 的时间拷贝path到结果集、判断nums[i] not in path也需要线性时间总复杂度为 $O(n \times n!)$。空间复杂度$O(n)$。递归过程中path最深为 $n$递归调用栈深度也为 $O(n)$不包含输出结果res本身占用的空间。需要注意回溯算法虽能保证找到所有解但时间复杂度通常较高尤其在解空间很大时。实际工程中可结合剪枝优化来减少无效搜索路径手册总结中对此有专门论述。优化与变体含重复元素的全排列如果输入数组包含重复数字即 LeetCode 0047「全排列 II」就不能再用nums[i] not in path直接判重否则会产生大量重复排列如[1,1,2]会重复生成[1,1,2]。手册的全排列 II 题解给出的做法是先排序对nums排序让相同元素相邻便于去重引入visited数组用visited[i]标记下标i的元素在当前排列中是否已被选用这比not in的线性查找更高效在递归前判重if i 0 and nums[i] nums[i - 1] and not visited[i - 1]: continue即当相邻重复元素中前一个还没被使用时跳过当前分支避免在同一层产生重复选择。核心代码如下class Solution: res [] path [] def backtrack(self, nums: List[int], visited: List[bool]): if len(self.path) len(nums): self.res.append(self.path[:]) return for i in range(len(nums)): if i 0 and nums[i] nums[i - 1] and not visited[i - 1]: continue if not visited[i]: visited[i] True self.path.append(nums[i]) self.backtrack(nums, visited) self.path.pop() visited[i] False def permuteUnique(self, nums: List[int]) - List[List[int]]: self.res.clear() self.path.clear() nums.sort() visited [False for _ in range(len(nums))] self.backtrack(nums, visited) return self.res对比可见visited数组本质上是对「nums[i] not in path」的通用化改造它在支持 O(1) 判重的同时也为「相同元素按顺序使用」的去重策略提供了条件前一个相同元素未被使用则跳过。该变体同样可在回溯算法题目列表中找到标签为「数组、回溯、排序」。与子集问题的对比为什么全排列要从头枚举把全排列与子集题解放在一起对比能更深刻地理解回溯中「约束条件」的作用子集{1,2}与{2,1}等价因此遍历时从index开始而不是从0开始避免重复考虑已枚举过的组合每次递归都会把当前path包括中间状态加入结果集全排列[1,2,3]与[3,2,1]是不同排列因此每层都必须从0开始枚举全部元素靠「当前路径中是否已包含该元素」作为约束来排除已选元素只有叶子节点路径长度等于数组长度才计入结果。这一对比说明回溯的「可选列表」与「约束条件」共同决定了搜索空间的形状是解决排列、组合、子集三类问题时最需要想清楚的设计点。相关题目与延伸路径全排列是回溯入门的第一道题掌握后可沿以下路径在手册中继续进阶全部对应仓库内题解0047. 全排列 II去重变体掌握排序 visited判重0078. 子集 与 0090. 子集 II组合类问题理解「从 index 开始」与去重的差异0039. 组合总和 与 0040. 组合总和 II带元素可重复使用的回溯0017. 电话号码的字母组合、0022. 括号生成字符串回溯0037. 解数独、0051. N 皇后棋盘类回溯进一步体会「约束条件」的复杂度完整列表见手册的回溯算法题目分类表。总结LeetCode 0046「全排列」用最简洁的代码演示了回溯算法的完整范式「明确所有选择决策树→ 明确终止条件叶子节点→ 翻译成代码选择 / 递归 / 撤销」。掌握res与path的职责划分、path[:]拷贝的必要性、以及nums[i] not in path的约束写法之后无论面对去重全排列 II、组合子集、还是棋盘类问题N 皇后都能快速迁移这套「选择 - 递归 - 回溯」的骨架这也是 AlgoNote 手册将其作为回溯算法第一道例题的原因。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册回溯算法原理、通用模板与全排列/子集/N 皇后实战解析AlgoNote 算法通关手册回溯算法原理、通用模板与全排列/子集/N 皇后实战解析 回溯算法Backtracking是一种通过「递归 试错」系统性穷教程文档知识库AlgoNote 算法通关手册枚举算法Enumeration Algorithm详解与实战AlgoNote 算法通关手册枚举算法Enumeration Algorithm详解与实战 导读 本文是「算法通关手册」第 7 章《算法》的开篇内容系统教程文档知识库LeetCode-Solutions-in-Good-Style回溯算法深度解析LeetCode Solutions in Good Style回溯算法深度解析 回溯算法是解决LeetCode难题的强大武器它通过深度优先搜索探索所有可能的上一篇Qwen3.6-27B-Aggressive深度解析从Q2到Q8的量化性能实战指南下一篇BeeftextWindows平台的终极文本片段管理工具10倍提升你的工作效率创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考