全排列
Permutations
给定一个不含重复数字的数组，返回它所有可能的全排列，顺序不限。
在力扣中练习题目描述
给定一个不含重复数字的数组 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]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
解题思路
回溯 · used 数组
每一位枚举一个没用过的数，回头时把选择撤销
最直接的想法是「每一位枚举一个没用过的数字」，这本身就是一棵决策树：第 1 层 n 个分支，第 2 层 n-1 个……叶子数正好是 n!，也就是答案的个数。
使用自拟输入 [-2, 5, 1]，共得到 6 个排列。先跟随第一个排列的产生与撤销，再观察三个首位分支如何完成，重点看恢复现场，而不是逐个重复所有排列。
path、res 为空，used 全为 false，进入第 0 层调用。
难点不在枚举，而在怎么在回头时恢复现场。递归时维护两个东西：
path：当前已经选好的前缀；used[i]：nums[i]是否已经在path里。
每一层固定做三步：
做选择：used[i] = true; path.push_back(nums[i])
递归： backtrack(nums, used, path, res)
撤销： path.pop_back(); used[i] = false
当 path.size() == n 时说明凑满了一个排列，把它复制进 res 再返回。必须复制：path 从头到尾是同一个对象，回溯过程中还会被反复改写。
撤销才是回溯的灵魂。不把 used[i] 改回 false，这个数字在兄弟分支里就永远用不上了；不 pop 掉 path 末尾，下一层会越积越长。
路径已满，复制 [-2, 5, 1] 到 res。
6 条路径全部走完，整棵树长这样：
树只增不减：走过的分支一直留在图上；真正被撤销的是 path 和 used，它们始终只保留当前这一条路径。层数等于位置数，第 1 层选第 1 位、第 2 层选第 2 位，所以每个叶子都对应一个完整排列。
易错点
- 收集结果后忘记 return，会继续往 path 里塞数字，导致越界或重复。
- 只撤销 path 不撤销 used，后面的分支会误以为这个数字还被占着。
- res 里存了 path 的引用而不是拷贝，最后所有结果都会变成同一个空数组。
交换法 · 原地回溯
把第 start 位和后面每个位置交换，省掉 used 数组
正确的交换回溯，在数组上原地安排位置；避免 used 数组，但必须在返回后恢复交换。
换一个视角看「枚举每一位」：第 start 位可以是 nums[start..n-1] 里的任意一个。那就把候选直接换到 start 上：
for i in [start, n):
swap(nums[start], nums[i]) // 让 nums[i] 坐镇第 start 位
dfs(start + 1)
swap(nums[start], nums[i]) // 换回来
这样 nums[0..start-1] 天然就是「已经确定的前缀」，nums[start..] 是剩下的候选池，不需要额外的 used 数组。
代价是会打乱 nums 的原始顺序（最后换回来时整体恢复，但中间过程是乱的）。如果题目要求输出按字典序，或者存在重复元素需要「同层去重」，还是用 used 版本更好控制。
复杂度一样：n! 个叶子，每个叶子复制一份长度 n 的数组。
- 1dfs(start)：start 表示当前要确定的位置。
- 2start == n 说明所有位置都定好了，把 nums 收进 res。
- 3i 从 start 枚举到 n-1，交换 nums[start] 与 nums[i]。
- 4递归 dfs(start + 1)，返回后再交换回来。
易错点
- 递归返回后忘记换回来，后面的分支会拿到被改乱的数组。
- 把 start 写成 0，会重复枚举整个数组，产生重复排列。
- 想按字典序输出时用这个写法要先想清楚交换顺序，否则结果是无序的。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [-2, 5, 1]path、res 为空，used 全为 false，进入第 0 层调用。
查看 C++ 代码
延伸阅读
- 答案本身就有 n! 个，每个长度 n，所以 O(n × n!) 已经是理论下界，不存在更快的枚举方式。
- 「做选择 → 递归 → 撤销」是所有回溯题的骨架：组合总和（39）、子集（78）、N 皇后（51）都是同一套模板换判断条件。
- 数组里有重复数字时（47 全排列 II），先排序，再跳过「同层相同且前一个还没用过」的分支。