题目
全排列 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
28
29
30
31
| class Solution {
public:
vector<vector<int>> res;
vector<bool> used;
void dfs(vector<int>& nums, vector<int>& arr){
if(arr.size() == nums.size()){
res.push_back(arr);
}
int x = -11;
for(int i = 0; i < nums.size(); i++){
if(x == nums[i]) continue;
if(!used[i]){
used[i] = true;
arr.push_back(nums[i]);
dfs(nums, arr);
used[i] = false;
x = arr[arr.size() - 1];
arr.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++) used.push_back(false);
vector<int> arr;
dfs(nums, arr);
return res;
}
};
|
- 时间复杂度：O(n n!)*
- 空间复杂度：O( n)，结果数组中最多有 n 个元素的数组
执行用时：4 ms, 在所有 C++ 提交中击败了91.98%的用户
内存消耗：8.7 MB, 在所有 C++ 提交中击败了56.14%的用户
通过测试用例：33 / 33