力扣46题：全排列 详细解题教程
题目描述
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]解题思路
本题是经典的回溯算法应用题。回溯法本质上是一种深度优先搜索（DFS），它通过尝试所有可能的选择，并在选择后发现不满足条件时“回溯”到上一步，撤销刚才的选择，尝试其他选项，从而遍历所有解空间。
对于全排列问题，我们需要生成所有可能的排列，每个排列由给定的数字组成，且每个数字恰好出现一次。我们可以想象成：我们需要往一个空列表（称为“路径”）中依次放入数字，每次从剩余未使用的数字中选一个放入，直到所有数字都被使用，此时得到一个排列。
回溯三要素
- 路径（track）：已经做出的选择，即当前已形成的部分排列。
- 选择列表：当前可以选择的数字，即尚未被使用的数字。
- 结束条件：当路径的长度等于原数组长度时，说明所有数字都已使用，得到一个完整排列，将其加入结果集。
算法步骤
- 初始化一个空列表
track用于记录当前路径，一个布尔数组used用于标记哪些数字已经被使用（初始全为false）。 - 定义一个递归函数
backtrack()，它没有参数，但可以访问外部的nums,track,used和结果集res。 - 在
backtrack中：- 如果
track.length === nums.length，说明已经得到一个完整排列，将track的拷贝加入结果集，然后返回。 - 否则，遍历数组
nums的每个索引i：- 如果
used[i]为true，说明该数字已经使用过，跳过。 - 否则，做选择：
- 将
nums[i]加入track。 - 将
used[i]设为true。 - 递归调用
backtrack()，进入下一层决策。 - 撤销选择（回溯）：
- 将
used[i]设回false。 - 将
track的最后一个元素弹出。
- 将
- 将
- 如果
- 如果
- 首次调用
backtrack()，从空路径开始。
递归树图解
以 nums = [1,2,3] 为例，画出递归树：
开始：路径=[], 可用={1,2,3}
├─ 选择1 → 路径=[1], 可用={2,3}
│ ├─ 选择2 → 路径=[1,2], 可用={3}
│ │ └─ 选择3 → 路径=[1,2,3] ✔ 记录
│ └─ 选择3 → 路径=[1,3], 可用={2}
│ └─ 选择2 → 路径=[1,3,2] ✔ 记录
├─ 选择2 → 路径=[2], 可用={1,3}
│ ├─ 选择1 → 路径=[2,1], 可用={3}
│ │ └─ 选择3 → 路径=[2,1,3] ✔
│ └─ 选择3 → 路径=[2,3], 可用={1}
│ └─ 选择1 → 路径=[2,3,1] ✔
└─ 选择3 → 路径=[3], 可用={1,2}
├─ 选择1 → 路径=[3,1], 可用={2}
│ └─ 选择2 → 路径=[3,1,2] ✔
└─ 选择2 → 路径=[3,2], 可用={1}
└─ 选择1 → 路径=[3,2,1] ✔从根节点到每个叶子节点的路径就是一个全排列，共 3! = 6 个。
代码实现（JavaScript）
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const res = []; // 存储所有排列结果
const track = []; // 记录当前路径
const used = new Array(nums.length).fill(false); // 标记数字是否被使用
function backtrack() {
// 结束条件：路径长度等于数组长度，得到一个完整排列
if (track.length === nums.length) {
res.push([...track]); // 注意要拷贝一份，因为 track 会变化
return;
}
// 遍历所有选择
for (let i = 0; i < nums.length; i++) {
// 如果当前数字已经使用过，跳过
if (used[i]) continue;
// 做选择
track.push(nums[i]);
used[i] = true;
// 进入下一层决策树
backtrack();
// 撤销选择（回溯）
track.pop();
used[i] = false;
}
}
backtrack();
return res;
};关键点解析
为什么需要
used数组？
因为排列中每个数字只能使用一次，所以需要记录哪些数字已经被选过。如果不加限制，就会产生重复或错误的结果。为什么
res.push([...track])要拷贝？track是一个数组，在后续回溯过程中会不断变化。如果直接res.push(track)，那么最终res中所有元素都会指向同一个数组引用，最后该数组会被清空，导致结果错误。因此需要创建一个副本。回溯的核心：在递归调用之后，必须撤销刚才所做的选择，这样才能让程序回到上一个状态，尝试其他分支。
时间复杂度：O(n × n!)，其中 n 为数组长度。因为全排列共有 n! 个，每个排列需要 O(n) 时间复制到结果中。递归树的节点数也是 n! 级别。
空间复杂度：O(n)，递归栈的深度为 n，加上
track和used数组，不考虑存储结果的空间。
常见问题与优化
输入有重复数字怎么办？
本题保证不含重复数字，所以直接使用即可。如果包含重复数字，则需要先排序并在同一层中跳过相同数字，以避免重复排列。能否不使用
used数组？
可以，但需要另一种方式：每次从剩余数字中选，可以用一个path和原数组，通过交换元素来实现（即“交换法”）。但used数组法更直观易懂。
解析回溯
在力扣46题“全排列”中，回溯是为了枚举所有可能的排列。我们可以通过一个生活中的例子来理解：
假设你要把三个不同颜色的球（红、绿、蓝）排成一行，你想找出所有可能的排列顺序。你会这样做：
- 先选第一个位置放什么球。假如你选了红球。
- 然后在剩下的两个球（绿、蓝）中选第二个位置。假如你选了绿球。
- 最后第三个位置只能放蓝球，得到一种排列：红、绿、蓝。
现在你得到了一个排列。但你还想得到红、蓝、绿这个排列。你该怎么办？你需要回到你选第二个位置的那个时刻，当时你选了绿球，但你可以改选蓝球。于是你撤销刚才的选择（把绿球放回去），然后改选蓝球，最后剩下的绿球放第三个位置，得到红、蓝、绿。
接着，你还想得到以绿球开头的排列。你需要再回到最初选第一个位置的时刻，把红球放回去，改选绿球作为第一个，然后重复上面的过程。
这个过程就是“回溯”：当你走完一条路（得到一个排列）后，你返回到上一个决策点，把刚才做出的选择撤销，恢复成没选之前的状态，然后尝试其他的选择。
在代码中，回溯体现在哪里？
看这段核心代码：
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // 跳过已使用的数字
track.push(nums[i]); // 做选择
used[i] = true; // 标记已使用
backtrack(); // 进入下一层
track.pop(); // 撤销选择（回溯）
used[i] = false; // 撤销标记
}- 做选择：把当前数字加入路径，并标记为已使用。
- 递归：基于这个选择，继续向下探索（选第二个、第三个数字）。
- 撤销选择：当递归返回时，说明以当前数字开头的所有排列都已经探索完毕（或者已经到达叶子节点），此时我们需要把刚才加入的数字从路径中移除，并把标记恢复为未使用，这样当前循环才能继续尝试下一个数字。
如果不进行撤销，那么路径中会一直保留这个数字，标记也一直为已使用，当你尝试下一个数字时，会发现所有数字都被标记为已使用，无法继续，最终只能得到一个排列。
用递归树看回溯
以 nums = [1,2,3] 为例，递归树的局部如下：
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] ...（依次类推）- 从根
[]出发，先走左分支，选择1，到达[1]。 - 在
[1]节点，再走左分支，选择2，到达[1,2]。 - 在
[1,2]节点，只能选3，到达叶子[1,2,3]，记录结果。 - 记录后，回溯：从
[1,2,3]返回[1,2]，并撤销对3的选择（把3放回），此时[1,2]的状态恢复了。 - 然后继续在
[1,2]节点尝试下一个选择（已经没有其他选择了，因为3已经试过且被撤销了），所以返回[1]。 - 在
[1]节点，撤销对2的选择（把2放回），然后尝试下一个选择：选择3，到达[1,3]，再选2，得到[1,3,2]…… - 如此反复，直到所有分支都遍历完。
回溯确保了每个分支都能被独立地探索，而不会相互干扰。
一句话总结
回溯就是“撤销当前选择，恢复现场”，让我们能够在尝试完一条路径后，回到上一个岔路口，去走另一条没走过的路，从而穷举所有可能的排列。