本文最后编辑于 前，其中的内容可能需要更新。
题目描述：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
1
2
| 输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
示例 2：
1
2
| 输入：nums = [0,1]
输出：[[0,1],[1,0]]
|
示例 3：
提示：
- $1 <= nums.length <= 6$
- $-10 <= nums[i] <= 10$
nums 中的所有整数 互不相同
链接：
https://leetcode-cn.com/problems/permutations
题目分析
全排列也即题目中所给数字填在不同的位置构成的所有情况，我们可以按顺序从左到右填上数字，利用回溯的方法即可穷举所有的情况。我们需要填入的数字也即 nums 数组，如何标记已经填入的数字呢？一个方法是维护一个布尔数组用于记录，将已填入的数字标记为 true。每次填入时按顺序遍历，寻找未填入的数字进行填入，并更新这个标记。回溯之后记得将标记回溯为 false。
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
| class Solution {
void backtrack(vector<vector<int>>& result, vector<int>& now, vector<int>& nums, vector<bool>& flag, int cnt){
if(cnt == nums.size()){
result.push_back(now);
return;
}
for(int i = 0; i < nums.size(); i++){
if(!flag[i]){
now.push_back(nums[i]);
flag[i] = true;
backtrack(result, now, nums, flag, cnt+1);
now.pop_back();
flag[i] = false;
}
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> now;
vector<bool> flag(nums.size(), false);
backtrack(result, now, nums, flag, 0);
return result;
}
};
|
上面的代码我们可以发现，每一次填数时，都需要遍历 flag 数组寻找未填入的数字，这样需要的时间更长，也需要额外的空间，有没有什么办法可以不需要这个标记数组呢？答案是肯定的。我们可以将 nums 数组分割为两个部分，一部分表示已经填入的数，一部分表示未填入的数，每次填入一个数，就将其与分割线的位置交换，例如 {2, 3, | 4, 5, 6} 这样的数组，下一个填入 6 时就将 4 与 6 交换，并且移动分割线，变成 {2, 3, 6, | 5, 4}，这样每次只需要从分割线的位置开始遍历就可以了，并且不需要额外的空间进行标记。值得注意的是，这样的交换会打乱数组的顺序，所以最后输出的结果并不是按照字典序来排列的。题目中说明可以按照任意顺序返回答案，因此可以这样做，如果有要求按照字典序，则只能按照上面的做法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
void backtrack(vector<vector<int>>& result, vector<int>& now, vector<int>& nums, int begin){
if(begin == nums.size()){
result.push_back(now);
return;
}
for(int i = begin; i < nums.size(); i++){
now.push_back(nums[i]);
swap(nums[begin], nums[i]);
backtrack(result, now, nums, begin+1);
now.pop_back();
swap(nums[begin], nums[i]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> now;
backtrack(result, now, nums, 0);
return result;
}
};
|
时间复杂度：$O(n\times n!)$，其中 $n$ 是数组的大小。因为我们遍历了所有的排列，全排列的个数为 $n!$。 而对于每一个解，我们都需要 $O(n)$ 的时间将其复制到答案数组中，因此总的时间复杂度为 $O(n\times n!)$。
空间复杂度：$O(n)$，其中 $n$ 是数组的大小。因为作为答案返回的数组不计入所需空间中，而我们需要的额外空间即递归调用的深度，最大深度为 $n$。
官方题解
看完官方题解才发现，我们在动态维护的 nums 数组，左边表示的已填入的数字就是按照填入的顺序进行排列的，因此可以不用额外的一个 now 数组对结果进行存储，在填完所有的数字后 nums 即为这种排列本身，将其复制到答案中即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
swap(output[i], output[first]);
backtrack(res, output, first + 1, len);
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
|