题目
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
分析
标记数组
每次枚举一个位置$pos$的可能的值，当前枚举的值在标记数组中标记，然后继续枚举下一个位置。
代码
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
28
29
| class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
cur = vector<int>(nums.size(), 0);
vis = vector<bool>(nums.size(), false);
backtrace(nums, 0);
return ans;
}
void backtrack(vector<int>& nums, int pos)
{
if (pos == nums.size())
{
ans.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (vis[i]) continue;
vis[i] = true;
cur[pos] = nums[i];
backtrace(nums, pos + 1);
vis[i] = false;
}
}
private:
vector<vector<int>> ans;
vector<int> cur;
vector<bool> vis;
};
|
空间复杂度：$O(n)$
原地
我们可以将当前枚举的元素交换到数组的前端，使得$[0, pos]$的元素是枚举过的元素，而$[pos + 1, n - 1]$的元素是尚未枚举过的元素，这样枚举下个位置的时候直接从$pos+1$开始枚举，就能保证枚举的元素一定是未枚举过的元素。
代码
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:
vector<vector<int>> permute(vector<int>& nums) {
backtrack(nums, 0);
return ans;
}
void backtrack(vector<int> &nums, int pos)
{
if (pos == nums.size())
{
ans.push_back(nums);
return;
}
for (int i = pos; i < nums.size(); ++i)
{
swap(nums[i], nums[pos]);
backtrack(nums, pos + 1);
swap(nums[i], nums[pos]);
}
}
private:
vector<vector<int>> ans;
};
|
空间复杂度：$O(1)$.