Hot 100 --- 全排列

本文概览：本文以LeetCode题目"全排列"为例，讲解回溯法的核心思路——已选择/未选择的划分，visited数组维护顺序，回溯就是撤销选择换下一个

一、题目

二、题目分析

题目要求：给定一个没有重复数字的数组，返回所有可能的全排列

全排列其实是初高中常遇到的数学题——n 个元素能排成多少个序列？答案是 n!。过程是这样的：

第1次选择：从 n 个元素里选 1 个 → n 种 第2次选择：从剩下的 n-1 个里选 1 个 → n-1 种 第3次选择：从剩下的 n-2 个里选 1 个 → n-2 种 ... 第n次选择：只剩 1 个，没得选 → 1 种 总排列数 = n × (n-1 × (n-2 × ... × 1)) = n!

这题的难点不是思路，而是怎么不重不漏地遍历完所有排列。如果随便选，必然会有重复。所以必须按某种顺序系统地遍历，这就需要回溯法

思路概览

classSolution{publicList<List<Integer>>permute(int[]nums){// 结果列表List<List<Integer>>res=newArrayList<>();if(nums.length==0){returnres;}// 访问数组boolean[]visited=newboolean[nums.length];// 递归函数backtrack(res,visited,nums,newArrayList<>());returnres;}privatevoidbacktrack(List<List<Integer>>res,boolean[]visited,int[]nums,ArrayList<Integer>path){// 递归出口if(path.size()==nums.length){res.add(newArrayList<>(path));return;}for(inti=0;i<nums.length;i++){// 剪枝if(visited[i]){continue;}// 标记访问过visited[i]=true;// 添加到当前路径path.add(nums[i]);// 递归调用backtrack(res,visited,nums,path);// 回溯visited[i]=false;// 从当前路径中移除path.removeLast();}}}

思路简要说明

1. 已选择 / 未选择：用 path 记录已选的元素，用 visited 数组记录每个元素有没有被选过（false = 没选过）。每轮从 i=0 扫到末尾，跳过选过的，选没选过的
2. 回溯 = 撤销选择换下一个：递归回来后，撤销当前选择（visited 设回 false，path 移除最后一个），for 循环 i++ 自动选下一个元素。这就实现了"选完一个换下一个试试"

三、思路详解

第一步：已选择 / 未选择的划分

回忆前面做过的题——无论 DFS 还是 BFS，我们都需要知道"已经处理了什么，还没处理什么"。全排列也一样，可以把数组分成两部分：

• 已选择：已经加入排列的元素，用 path 列表记录
• 未选择：还没加入排列的元素，用 visited 数组标记（false 表示未选择）

以 nums = [1, 2, 3] 为例： 初始状态： 已选择 path = [] 未选择 visited = [false, false, false] → 1, 2, 3 都可选 选了 1 之后： 已选择 path = [1] 未选择 visited = [true, false, false] → 2, 3 可选 再选了 2 之后： 已选择 path = [1, 2] 未选择 visited = [true, true, false] → 只有 3 可选

第二步：怎么保证不重不漏？

这是这题的核心问题。如果随便选，比如先选 2 再选 1，和先选 1 再选 2，可能会产生重复的遍历路径

解决办法很简单：每一轮都从 i=0 开始扫描，遇到选过的就跳过，选第一个没选过的。因为 for 循环永远从 0 开始，选过的元素会被if (visited[i]) continue跳过，没选过的元素会按数组下标顺序依次被选中

nums = [1, 2, 3]，假设 1 已经选过了： i=0: visited[0]=true → 跳过 i=1: visited[1]=false → 选 2 i=2: visited[2]=false → 选 3 没选过的 2、3 会按数组顺序被选到，不会乱

每次都是按固定顺序选，不可能产生重复

第三步：回溯是什么？

回溯就是撤销当前选择，换下一个试试

用 nums = [1, 2, 3] 举例，手动模拟一遍全过程：

第一轮：全选第一个 选 1 → path = [1] 选 2 → path = [1, 2] 选 3 → path = [1, 2, 3] ✓ 第1个排列 回溯：撤销 3，path = [1, 2] 没有其他可选了 回溯：撤销 2，path = [1] 选 3 → path = [1, 3] 选 2 → path = [1, 3, 2] ✓ 第2个排列 回溯：撤销 2，path = [1, 3] 没有其他可选了 回溯：撤销 3，path = [1] 没有其他可选了 回溯：撤销 1，path = [] 第二轮：从倒数第二个开始换 选 2 → path = [2] 选 1 → path = [2, 1] 选 3 → path = [2, 1, 3] ✓ 第3个排列 ... 选 3 → path = [2, 3] 选 1 → path = [2, 3, 1] ✓ 第4个排列 ... 回溯：撤销 2，path = [] 第三轮：换到第一个位置的第三个元素 选 3 → path = [3] 选 1 → path = [3, 1] 选 2 → path = [3, 1, 2] ✓ 第5个排列 ... 选 2 → path = [3, 2] 选 1 → path = [3, 2, 1] ✓ 第6个排列 ... 回溯：撤销 3，path = []

6 个排列，正好是 3! = 6。观察整个过程：

• 第一轮全选第一个，得到 [1,2,3]
• 然后从倒数第二个开始回溯，换一个选择，得到 [1,3,2]
• 再往上一层回溯，从倒数第三个开始换，选第二个元素 2，然后重复第一轮第二轮的操作
• 再从倒数第三个换到第三个元素 3，重复操作

这就是回溯的本质——从最深处开始撤销，换一个选择，换完后继续往下走；这一层换完了就退到上一层再换

第四步：代码怎么对应这个过程？

for(inti=0;i<nums.length;i++){if(visited[i])continue;// ① 跳过已选的visited[i]=true;// ② 标记选择path.add(nums[i]);// ③ 加入路径backtrack(...);// ④ 往下递归visited[i]=false;// ⑤ 回溯：撤销标记path.removeLast();// ⑥ 回溯：移出路径}

• ①②③：选择当前元素
• ④：带着这个选择往下走，处理剩余元素
• ⑤⑥：递归回来后撤销选择，for 循环 i++ 自动选下一个

for 循环就是"遍历所有可选元素"，回溯就是"选完了换下一个"。不需要手动控制"从倒数第几个开始换"——for 循环 + 递归自然就实现了这个逻辑

第五步：递归出口

if(path.size()==nums.length){res.add(newArrayList<>(path));return;}

当 path 的长度等于 nums 的长度时，说明所有元素都选完了，这是一个完整的排列。注意要用new ArrayList<>(path)创建副本——如果直接 add(path)，后续回溯修改 path 会影响已经存入的结果

第六步：完整执行过程图解

以 nums = [1, 2, 3] 为例，用缩进表示递归深度：

path = [] visited = [F, F, F] i=0: 选 1 → path = [1] visited = [T, F, F] i=0: 跳过（已访问） i=1: 选 2 → path = [1,2] visited = [T, T, F] i=0: 跳过 i=1: 跳过 i=2: 选 3 → path = [1,2,3] ✓ 加入结果 回溯：path = [1,2] visited = [T, T, F] 回溯：path = [1] visited = [T, F, F] i=2: 选 3 → path = [1,3] visited = [T, F, T] i=0: 跳过 i=1: 选 2 → path = [1,3,2] ✓ 加入结果 回溯：path = [1,3] 回溯：path = [1] 回溯：path = [] visited = [F, F, F] i=1: 选 2 → path = [2] visited = [F, T, F] i=0: 选 1 → path = [2,1] visited = [T, T, F] i=2: 选 3 → path = [2,1,3] ✓ 加入结果 回溯... i=2: 选 3 → path = [2,3] visited = [F, T, T] i=0: 选 1 → path = [2,3,1] ✓ 加入结果 回溯... 回溯：path = [] i=2: 选 3 → path = [3] visited = [F, F, T] i=0: 选 1 → path = [3,1] visited = [T, F, T] i=1: 选 2 → path = [3,1,2] ✓ 加入结果 回溯... i=1: 选 2 → path = [3,2] visited = [F, T, T] i=0: 选 1 → path = [3,2,1] ✓ 加入结果 回溯... 回溯：path = []

最终结果：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]，共 6 个

复杂度分析

• 时间复杂度：O(n × n!)，共 n! 个排列，每个排列需要 O(n) 时间复制到结果
• 空间复杂度：O(n)，递归深度最大为 n，visited 数组和 path 都是 O(n)