LeetCode 46. 全排列——回溯模板：visited数组与swap两种实现
LeetCode 46. 全排列——回溯模板：visited数组与swap两种实现
适读人群：Java初中级工程师、算法学习入门者 | 阅读时长：约20分钟 | 难度：中等
开篇故事
从贪心篇进入回溯篇，感觉就像从"确定性"走入了"不确定性"。贪心每次做出一个局部最优选择，义无反顾向前走；回溯则是"试错式"——尝试每一种可能，走不通就撤回，再试另一条路。
我第一次接触回溯算法是在大二的数据结构课上，老师讲八皇后问题，满黑板地画"探索-回退"的树。那时候我没完全听懂，但有一个画面很清晰：一棵决策树，每个节点代表一个选择，从根走到叶子是一条完整的方案，如果走到某个节点发现"此路不通"就退回父节点，换另一个方向继续。
这就是回溯的本质。全排列是回溯的入门题，也是最好的起点。这道题有两种实现方式：visited 数组和 swap，各有各的优势。今天把这两种方式都讲透，建立你自己的回溯框架。
一、题目解析
题目： 给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例：
- 输入：nums = [1,2,3]，输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
- 输入：nums = [0,1]，输出：[[0,1],[1,0]]
- 输入：nums = [1]，输出：[[1]]
关键约束： nums 中的整数互不相同（无重复元素），这是与下一题的核心区别。
问题分析：
全排列的数量是 n!（n 阶乘）：
- n=3：3! = 6
- n=6：6! = 720
- n=9（题目上限）：9! = 362880
因为结果数量本身就是 O(n!)，任何算法的时间复杂度至少是 O(n! × n)（n! 个排列，每个排列长度 n），所以不存在更快的渐进复杂度。
回溯框架：
backtrack(当前路径, 可用元素集合):
if 路径长度 == n:
记录当前路径为一个结果
return
for 每个可用元素 e:
将 e 加入路径
从可用集合中移除 e
backtrack(更新后的路径, 更新后的可用集合)
将 e 从路径中移除（回溯）
将 e 放回可用集合二、解法一：visited 数组标记（标准回溯模板）
思路
用一个 boolean[] visited 数组标记哪些元素已经在当前路径中使用。回溯时，选一个未使用的元素加入路径，递归之后撤销选择。
代码
import java.util.*;
public class Solution_Visited {
private List<List<Integer>> result = new ArrayList<>();
private boolean[] visited;
public List<List<Integer>> permute(int[] nums) {
visited = new boolean[nums.length];
backtrack(nums, new ArrayList<>());
return result;
}
private void backtrack(int[] nums, List<Integer> path) {
// 终止条件：路径长度等于数组长度，找到一个完整排列
if (path.size() == nums.length) {
result.add(new ArrayList<>(path)); // 注意：要复制 path，而不是直接引用
return;
}
// 遍历所有候选元素
for (int i = 0; i < nums.length; i++) {
if (visited[i]) continue; // 已使用，跳过
// 做选择
path.add(nums[i]);
visited[i] = true;
// 递归进入下一层
backtrack(nums, path);
// 撤销选择（回溯）
path.remove(path.size() - 1);
visited[i] = false;
}
}
}代码详解
result.add(new ArrayList<>(path))：必须用复制构造函数，不能直接result.add(path)。因为 path 是引用，后续回溯会修改 path 的内容，如果直接添加引用，最终 result 里所有元素都指向同一个 path，内容都是最后一个排列。path.remove(path.size() - 1)：移除最后一个元素，撤销上一步的选择。Java 的List.remove(int index)传入下标，path.size() - 1是最后一个元素的下标。visited[i] = false：撤销标记，让这个元素可以在其他分支中重复使用。
复杂度分析
- 时间复杂度： O(n! × n)——共 n! 个叶子节点，每次记录结果需要复制路径 O(n)；非叶子节点有 n + n(n-1) + ... = O(n!) 个，每个节点做常数工作。总体 O(n! × n)。
- 空间复杂度： O(n)，递归栈深度为 n，visited 数组和 path 各 O(n)。
三、解法二：swap 原地交换（不需要 visited 数组）
思路
原地交换的思想：将数组分为"已选部分"（下标 0..depth-1）和"待选部分"（下标 depth..n-1）。每次从待选部分选一个元素，与 depth 位置的元素交换，然后递归处理 depth+1。递归返回后，再交换回来（回溯）。
这样不需要 visited 数组和额外的 path 列表，空间更省。
可视化：
初始: [1, 2, 3], depth=0
选1(不换): depth=1, [1, 2, 3]
选2(不换): depth=2, [1, 2, 3]
depth=3=n, 记录[1,2,3]
回溯: [1, 2, 3]
选3(swap 2和3): depth=2, [1, 3, 2]
depth=3=n, 记录[1,3,2]
回溯: swap还原, [1, 2, 3]
回溯: [1, 2, 3]
选2(swap 0和1): depth=1, [2, 1, 3]
...
...代码
import java.util.*;
public class Solution_Swap {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
backtrack(nums, 0);
return result;
}
private void backtrack(int[] nums, int depth) {
// 终止条件：已选定了 n 个元素（depth == n）
if (depth == nums.length) {
// 将当前 nums 转为 List 记录结果
List<Integer> perm = new ArrayList<>();
for (int num : nums) perm.add(num);
result.add(perm);
return;
}
// 从 depth 到 n-1 依次选择每个元素放到 depth 位置
for (int i = depth; i < nums.length; i++) {
// 将 nums[i] 换到 depth 位置
swap(nums, depth, i);
// 递归处理 depth+1 到 n-1 的排列
backtrack(nums, depth + 1);
// 换回来（回溯）
swap(nums, depth, i);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}Mermaid 图：swap 方式的递归树（n=3）
复杂度分析
- 时间复杂度： O(n! × n)，与解法一相同。
- 空间复杂度： O(n)，递归栈深度 n。比解法一省去了 visited 数组，但需要将 nums 转为 List，整体同级别。
四、解法三：迭代构建（BFS 风格）
思路
不用递归，用迭代方式逐步扩展排列。初始时 result 中只有一个空排列，每次将下一个数字插入到已有排列的所有可能位置，生成更长的排列。
代码
import java.util.*;
public class Solution_Iterative {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>()); // 初始：一个空排列
for (int num : nums) {
List<List<Integer>> newResult = new ArrayList<>();
for (List<Integer> perm : result) {
// 将 num 插入到当前排列的每个位置
for (int i = 0; i <= perm.size(); i++) {
List<Integer> newPerm = new ArrayList<>(perm);
newPerm.add(i, num); // 在位置 i 插入 num
newResult.add(newPerm);
}
}
result = newResult;
}
return result;
}
}执行过程（以 [1,2,3] 为例）：
- 初始：result = [[]]
- 处理 1：在 [] 的位置0插入1 → result = [[1]]
- 处理 2：在 [1] 的位置0插入2→[2,1]，位置1插入2→[1,2] → result = [[2,1],[1,2]]
- 处理 3：在 [2,1] 的3个位置，在 [1,2] 的3个位置 → result = 6个排列
复杂度分析
- 时间复杂度： O(n! × n)。
- 空间复杂度： O(n! × n)，同时存储所有中间状态。比回溯方式占用更多空间。
五、举一反三
回溯通用模板
void backtrack(参数) {
if (终止条件) {
收集结果;
return;
}
for (选择 : 候选集合) {
if (不满足约束) continue; // 剪枝
做选择;
backtrack(更新参数);
撤销选择; // 回溯
}
}相关题目
- LeetCode 47 全排列II：含重复元素，需要去重（下一篇详讲）
- LeetCode 77 组合：从 n 个中选 k 个，不关注顺序
- LeetCode 78 子集：选或不选，生成所有子集
- LeetCode 22 括号生成：隐式约束剪枝的回溯
六、踩坑实录
坑一：result.add(path) 而不是 result.add(new ArrayList<>(path))
这是回溯最经典的 bug，每个初学者都会踩。由于 path 是引用，回溯结束后 path 为空，result 中添加的所有元素实际上都指向同一个空 path。
// 错误：直接添加引用
result.add(path); // 最终result里所有元素都是空列表！
// 正确：复制一份新列表
result.add(new ArrayList<>(path));坑二：path.remove(index) 用错了重载
Java List 的 remove 方法有两个重载：
remove(int index)：按下标删除remove(Object o)：按值删除
当 List<Integer> 的元素是 Integer 时，path.remove(path.size()-1) 是按下标删除最后一个元素，这是正确的。但如果写成 path.remove(nums[i])，对于 int 类型，Java 会自动装箱为 Integer，调用 remove(Object o) 按值删除——如果数组中有重复值（本题无重复，但其他题有），可能删错元素。
坑三：swap 方式中 depth == i 的情况
当 i == depth 时，swap(nums, depth, i) 是自身与自身交换，相当于不交换（nums 不变）。这是正确的——它对应"选择当前 depth 位置的元素"。
坑四：回溯结束后 nums 是否恢复原样
swap 方式每次 swap 后会还原，所以 backtrack 结束后 nums 一定恢复到初始状态。但如果忘记回溯（漏写了第二个 swap），nums 会被永久修改，导致后续分支结果错误。
坑五：递归深度与 nums.length 的关系
visited 方式用 path.size() == nums.length 作终止条件，swap 方式用 depth == nums.length。两者等价。但不要把 depth 和 i 搞混——depth 是"已选了几个"，i 是"当前候选的下标"。
七、总结
全排列是回溯入门的最佳题目，两种实现方式各有特点：
- visited 数组：思路更清晰，代码更直观，适合初学者。每次从整个数组中选一个未用的元素，通过 visited 标记来避免重复选取。
- swap 原地交换：空间更省（不需要 visited 数组和 path）。通过将"待选部分"和"已选部分"用数组分隔来实现，适合熟悉了 visited 方式后的进阶写法。
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| visited 数组 | O(n! × n) | O(n) | 初学者，逻辑清晰 |
| swap 交换 | O(n! × n) | O(n) | 进阶，空间更省 |
| 迭代BFS | O(n! × n) | O(n! × n) | 理解排列结构 |
两种方式都要掌握，因为后续的"含重复元素的全排列"（LeetCode 47）在去重处理上，两种方式的做法截然不同，各有各的优势。
补充深入讲解：回溯算法的本质与全排列的数学基础
为什么 new ArrayList<>(path) 是不可省略的
这个细节看似简单，却是理解回溯算法"状态管理"的核心。在整个回溯过程中，path 这个列表是被反复修改的——添加元素、删除元素，不停地改变内容。当我们找到一个完整排列时，path 中存的是当前这个排列的元素，我们想把这个排列"固化"下来存入结果集。
如果直接执行 result.add(path)，我们加入结果集的是 path 这个列表对象的引用，而不是它当前内容的快照。后续回溯继续执行，path 的内容会被修改，导致我们之前"存入"的那个结果也跟着变了。等到回溯全部结束，所有加入 result 的元素都指向同一个空的 path，结果全是空列表。
new ArrayList<>(path) 创建了一个新的 ArrayList 对象，把 path 当前的所有内容复制进去，形成一个独立的快照。这个新对象和 path 互相独立，后续对 path 的修改不会影响它。这是回溯算法中"收集结果"最关键的操作习惯。
在面试中，如果你写回溯，面试官最常抠的就是这个细节。写对了说明你真正理解了引用语义和对象生命周期，写错了即使整体思路正确，实际运行结果也会出问题。
决策树的数学结构
全排列的决策树有明确的数学结构。以 n=3 为例，树的形态是：
第0层（根节点）：1个节点，代表"尚未做任何选择"。 第1层：n=3 个节点，分别对应选择了 nums[0]、nums[1]、nums[2] 作为第一个元素。 第2层：n×(n-1)=6 个节点，每个第1层节点下有 n-1 个子节点，对应剩余 n-1 个元素的选择。 第3层（叶子节点）：n!=6 个叶子，每个叶子是一个完整排列。
非叶子节点总数 = 1 + n + n(n-1) + ... + n!/(n-k)! 对 k 从 0 到 n-1 求和。这个求和大约等于 e×n!（欧拉数 e≈2.718），也就是说非叶子节点数量是 O(n!)。
每个叶子节点需要 O(n) 时间复制结果，每个非叶子节点只做常数工作（循环迭代本身不计，循环内的工作才算）。所以总时间复杂度是 O(n! × n)，这是信息论意义上的最优：因为输出本身就有 n! 个长度为 n 的排列，输出量是 O(n! × n) 个字节，任何正确算法的时间复杂度至少是 O(n! × n)。
visited 方式与 swap 方式的深层对比
从表面上看，visited 方式和 swap 方式只是实现细节不同，但它们体现了两种不同的状态抽象。
visited 方式的抽象是"路径+可用集合"。状态由当前路径 path（已选的元素序列）和可用集合（visited=false 的元素集合）共同描述。这种抽象非常直观，对应了"排列 = 从可用元素中依次选择"的直觉理解。
swap 方式的抽象是"数组的前缀+后缀划分"。将原始数组 nums 划分为"已确定前缀"（下标 0..depth-1）和"待选后缀"（下标 depth..n-1），状态完全由 nums 数组本身和当前 depth 值描述。这种抽象更紧凑，因为不需要额外的 visited 数组或 path 列表，所有状态都编码在 nums 数组的重排列中。
两种抽象都正确，各有适用场景。visited 方式在处理含重复元素的排列（LeetCode 47）时，去重逻辑更自然：只需在选择前检查"同一位置的兄弟节点中是否已经选过相同值"。swap 方式在这种情况下去重逻辑较为复杂，需要借助辅助的 HashSet 来记录当前层已经选过的值。
回溯的时间优化：剪枝的价值
全排列（无重复元素）没有剪枝空间，因为任何元素序列都是合法排列，不存在"此路不通"的情况。但一旦加上约束（比如排列中相邻元素之差不能超过某个值，或者排列必须满足某种单调性），就有剪枝空间了。
剪枝的核心思想是：如果当前选择已经违反了约束，那么所有以当前路径为前缀的排列都不合法，可以直接截断这棵子树，避免枚举无效分支。剪枝能把回溯从"理论上 O(n!)"的穷举变成"实际上快很多"的算法，剪掉越多的分支，效率提升越显著。
全排列的变种题中，一类常见的剪枝场景是"带约束的全排列"，比如要求排列中某些元素必须在另一些元素之前（偏序约束）。这时候在每一步选择元素时，先检查"当前待选元素的所有前驱是否都已选入路径"，满足才选，否则跳过，这就是一种有效的剪枝。
全排列的工程应用场景
全排列在工程中的直接应用并不多见，因为 n! 增长极快，实际中很少需要枚举所有排列。但全排列的思想和框架有很多间接应用。
任务调度中的穷举优化：在任务数量很少（n<=10）的调度系统中，有时需要枚举所有任务执行顺序，找到总执行时间最短的方案（考虑任务间的等待时间和上下文切换开销）。这就是全排列的直接应用，n! 在 n=10 时约为 360 万，配合剪枝可以在秒级内完成。
测试用例的执行顺序：在某些有状态的系统测试中，测试用例的执行顺序可能影响结果（比如数据库状态测试）。为了发现与顺序相关的 bug，可以枚举所有可能的执行顺序，这也是全排列的应用。
密码学中的排列分析：某些密码算法的安全分析涉及计算特定排列的数量，全排列的生成算法是这类分析的基础工具。
这些场景说明全排列不只是一道算法题，而是计算机科学基础工具的一部分。
从全排列到其他枚举问题的思维迁移
全排列解决了"n 个不同元素的所有排列方式"问题，这是回溯框架的最简洁应用。学会全排列之后，你会发现很多更复杂的回溯问题，本质上都是全排列的变形或子集：
组合问题（LeetCode 77）是"n 中选 k 个，不关注顺序"，相当于在全排列的基础上消除了顺序，只保留每个组合的一种代表。子集问题（LeetCode 78）是"n 中选 0 到 n 个，不关注顺序"，是组合问题的推广。
含约束的排列（如相邻元素差至多为某值）则是在全排列基础上增加剪枝条件。图的哈密顿路径（经过图每个节点恰好一次的路径）是全排列与图约束的结合——也是 NP 完全问题，只能通过回溯+剪枝求解。
理解了全排列的两种实现（visited 数组和 swap），掌握了回溯的本质（做选择-递归-撤销），后续回溯题型的学习会事半功倍。每遇到一道回溯题，先思考"状态如何表示"、"如何枚举候选"、"什么时候剪枝"，就能在全排列的模板基础上快速搭建解法框架。
回溯框架的记忆技巧
全排列的回溯框架只需记住四个要素：终止条件（路径满了就记录）、候选集合（未使用的元素）、做选择（加入路径并标记）、撤销选择（从路径移除并取消标记）。四个要素理解了，全排列的代码就能手写出来，不需要死记硬背。