给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
方法 1：回溯法（经典解法）
核心思想
- 递归 + 回溯：每次选择一个未被使用的数字，放入当前路径，直到路径长度等于
nums.length。
- 维护
used 数组：记录哪些数字已经被使用过，避免重复选择。
JavaScript 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| var permute = function(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
const backtrack = (path) => {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
backtrack(path);
path.pop();
used[i] = false;
}
};
backtrack([]);
return result;
};
|
时间复杂度
- **O(n × n!)**：共有
n! 种排列，每种排列需要 O(n) 时间生成。
方法 2：交换法（更高效，原地修改）
核心思想
- 交换元素：通过交换
nums 中的元素，直接生成所有排列，无需 used 数组。
- 递归 + 回溯：固定一个位置，递归生成剩余部分的排列。
JavaScript 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| var permute = function(nums) {
const result = [];
const backtrack = (start) => {
if (start === nums.length) {
result.push([...nums]);
return;
}
for (let i = start; i < nums.length; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]];
backtrack(start + 1);
[nums[start], nums[i]] = [nums[i], nums[start]];
}
};
backtrack(0);
return result;
};
|
时间复杂度
- **O(n!)**：比方法 1 稍快，但仍是指数级。
方法 3：库函数（Python 适用）
在 Python 中，可以直接用 itertools.permutations：
1
2
3
4
| from itertools import permutations
def permute(nums):
return list(permutations(nums))
|
但 JavaScript 没有内置排列函数，需手动实现。
变种问题：全排列 II（含重复数字）
如果 nums 包含重复数字，需去重：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| var permuteUnique = function(nums) {
nums.sort((a, b) => a - b);
const result = [];
const used = new Array(nums.length).fill(false);
const backtrack = (path) => {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
continue;
}
used[i] = true;
path.push(nums[i]);
backtrack(path);
path.pop();
used[i] = false;
}
};
backtrack([]);
return result;
};
|
关键点：
- 排序：让相同数字相邻。
- 去重条件：
nums[i] === nums[i - 1]：当前数字和前一个相同。!used[i - 1]：前一个数字未被使用（避免重复选择）。
总结
| 方法 |
特点 |
时间复杂度 |
适用场景 |
回溯 + used 数组 |
直观，易理解 |
O(n × n!) |
通用 |
| 交换法 |
更高效，原地修改 |
O(n!) |
无需额外空间 |
| 库函数（Python） |
代码最短 |
- |
仅限 Python |
| 全排列 II（去重） |
需排序 + 去重逻辑 |
O(n × n!) |
含重复数字 |
推荐：
- 无重复数字：交换法（方法 2）。
- 含重复数字：回溯 + 排序去重（方法 1 变种）。