46. 全排列
题目描述
输入一个元素互不相同的整数数组 nums。
把 nums 的元素按所有可能的先后顺序排列，每种排法都用到全部元素各一次。返回所有排法，排法之间的顺序不限。
示例 1
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解释：3 个不同的数共有 3! = 6 种排法。
示例 2
输入：nums = [0,1] 输出：[[0,1],[1,0]]
解释：两个数有 2 种排法。
示例 3
输入：nums = [1] 输出：[[1]]
解释：只有一个数，只有一种排法。
数据范围
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的整数互不相同。
解题思路：回溯 + used 标记数组
回溯维护 path 与 used。
为什么正确
递归返回前恢复选择。
复杂度分析
时间 O(n·n!)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def permute(self,a):
out=[];p=[];u=[0]*len(a)
def f():
if len(p)==len(a):out.append(p[:]);return
for i,x in enumerate(a):
if not u[i]:u[i]=1;p.append(x);f();p.pop();u[i]=0
f();return outclass Solution {
private List<List<Integer>> out;
private List<Integer> p;
private int[] u;
public List<List<Integer>> permute(int[] nums) {
out = new ArrayList<>();
p = new ArrayList<>();
u = new int[nums.length];
f(nums);
return out;
}
private void f(int[] nums) {
if (p.size() == nums.length) {
out.add(new ArrayList<>(p));
return;
}
for (int i = 0; i < nums.length; i++) {
if (u[i] == 0) {
u[i] = 1;
p.add(nums[i]);
f(nums);
p.remove(p.size() - 1);
u[i] = 0;
}
}
}
}class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> out;
vector<int> p;
vector<int> u(nums.size(), 0);
function<void()> f = [&]() {
if (p.size() == nums.size()) {
out.push_back(p);
return;
}
for (int i = 0; i < (int)nums.size(); i++) {
if (!u[i]) {
u[i] = 1;
p.push_back(nums[i]);
f();
p.pop_back();
u[i] = 0;
}
}
};
f();
return out;
}
};func permute(nums []int) [][]int {
out := [][]int{}
p := []int{}
u := make([]int, len(nums))
var f func()
f = func() {
if len(p) == len(nums) {
out = append(out, append([]int{}, p...))
return
}
for i, x := range nums {
if u[i] == 0 {
u[i] = 1
p = append(p, x)
f()
p = p[:len(p)-1]
u[i] = 0
}
}
}
f()
return out
}var permute = function(nums) {
const out = [], p = [], u = new Array(nums.length).fill(0);
const f = () => {
if (p.length === nums.length) {
out.push([...p]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (!u[i]) {
u[i] = 1;
p.push(nums[i]);
f();
p.pop();
u[i] = 0;
}
}
};
f();
return out;
};function permute(nums: number[]): number[][] {
const out: number[][] = [], p: number[] = [], u: number[] = new Array(nums.length).fill(0);
const f = (): void => {
if (p.length === nums.length) {
out.push([...p]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (!u[i]) {
u[i] = 1;
p.push(nums[i]);
f();
p.pop();
u[i] = 0;
}
}
};
f();
return out;
};其他解法
used 写法每层扫描全部 n 个元素并跳过已用元素，产出字典序（输入有序时）；交换写法每层只遍历右侧未确定段，无需额外标记，但输出顺序被打乱。
解法 2：原地交换回溯 时间 O(n·n!)，空间 O(n)
把数组划分为两段：下标 first 左侧是已经确定的前缀，右侧是待选元素。第 first 层依次把 nums[i]（i ≥ first）交换到位置 first，递归处理 first+1，返回后再交换回来恢复现场。first 到达 n 时，整个数组就是一个排列。
不需要 used 数组和额外的路径数组，直接在原数组上生成排列，省去每层对 n 个元素的“是否已用”判断。缺点是生成顺序不是字典序；若输入有重复元素，去重也比 used 写法麻烦。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def dfs(first):
if first == n:
res.append(nums[:])
return
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
dfs(first + 1)
nums[first], nums[i] = nums[i], nums[first]
dfs(0)
return resclass Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
dfs(nums, 0);
return res;
}
void dfs(int[] nums, int first) {
if (first == nums.length) {
List<Integer> p = new ArrayList<>();
for (int x : nums) p.add(x);
res.add(p);
return;
}
for (int i = first; i < nums.length; i++) {
int t = nums[first]; nums[first] = nums[i]; nums[i] = t;
dfs(nums, first + 1);
t = nums[first]; nums[first] = nums[i]; nums[i] = t;
}
}
}class Solution {
public:
vector<vector<int>> res;
void dfs(vector<int>& nums, int first) {
if (first == (int)nums.size()) { res.push_back(nums); return; }
for (int i = first; i < (int)nums.size(); i++) {
swap(nums[first], nums[i]);
dfs(nums, first + 1);
swap(nums[first], nums[i]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
res.clear();
dfs(nums, 0);
return res;
}
};func permute(nums []int) [][]int {
res := [][]int{}
n := len(nums)
var dfs func(first int)
dfs = func(first int) {
if first == n {
res = append(res, append([]int{}, nums...))
return
}
for i := first; i < n; i++ {
nums[first], nums[i] = nums[i], nums[first]
dfs(first + 1)
nums[first], nums[i] = nums[i], nums[first]
}
}
dfs(0)
return res
}var permute = function(nums) {
const res = [], n = nums.length;
const dfs = (first) => {
if (first === n) { res.push([...nums]); return; }
for (let i = first; i < n; i++) {
[nums[first], nums[i]] = [nums[i], nums[first]];
dfs(first + 1);
[nums[first], nums[i]] = [nums[i], nums[first]];
}
};
dfs(0);
return res;
};function permute(nums: number[]): number[][] {
const res: number[][] = [], n = nums.length;
const dfs = (first: number): void => {
if (first === n) { res.push([...nums]); return; }
for (let i = first; i < n; i++) {
[nums[first], nums[i]] = [nums[i], nums[first]];
dfs(first + 1);
[nums[first], nums[i]] = [nums[i], nums[first]];
}
};
dfs(0);
return res;
}