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开始枚举全部元素，靠「当前路径中是否已包含该元素」作为约束来排除已选元素；只有叶子节点（路径长度等于数组长度）才计入结果。

这一对比说明：回溯的「可选列表」与「约束条件」共同决定了搜索空间的形状，是解决排列、组合、子集三类问题时最需要想清楚的设计点。

总结

LeetCode 0046「全排列」用最简洁的代码演示了回溯算法的完整范式：「明确所有选择（决策树）→ 明确终止条件（叶子节点）→ 翻译成代码（选择 / 递归 / 撤销）」。掌握res与path的职责划分、path[:]拷贝的必要性、以及nums[i] not in path的约束写法之后，无论面对去重（全排列 II）、组合（子集）、还是棋盘类问题（N 皇后），都能快速迁移这套「选择 - 递归 - 回溯」的骨架，这也是 AlgoNote 手册将其作为回溯算法第一道例题的原因。