给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。
提示：
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
47.全排列II
这种排列的很容易想到回溯，但是题目中给定的数组中可能包含重复数字，如果单纯地回溯可能造成枚举的重复。
为解决重复数字的问题，可以将数组排序，令相同数字相连在一起。对于相同的数字，令其在数组中出现的顺序相同，可以达到去重的效果。
本例中令相同的数字按顺序从左至右访问，如果该数访问过了或者前一个相同的数字未访问，则跳过。
当然也可以从右至左，评论区中有一则评论是这样的：
其实简单的来说，以[1,1,1,2]为例子
vis[i-1]==0时continue，那三个1的选取顺序只能是①②③
vis[i-1]==1时continue，那三个1的选取顺序只能是③②①
往后不管多少个相同的数字，都只有“顺序“或“逆序”的方式选取，而不会出现 ③①②、②①③ 等等
所以这里的排列是通过确定相同数字的选取顺序，二选一，来排除因其他选取顺序而产生的重复结果
反正大概就这个意思，我也懒得再解释了
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
| class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
int n = nums.size();
vector<int> vst(n, 0);
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> curr;
backTrack(nums, vst, 0, curr, ans);
return ans;
}
void backTrack(vector<int>& nums, vector<int>& vst, int idx, vector<int>& curr, vector<vector<int>>& ans){
int n = nums.size();
if(idx == n){
ans.push_back(curr);
}
for(int i = 0; i < n; ++i){
if(vst[i] || (i > 0 && !vst[i - 1] && nums[i] == nums[i - 1])){
continue;
}
vst[i] = 1;
curr.push_back(nums[i]);
backTrack(nums, vst, idx + 1, curr, ans);
curr.pop_back();
vst[i] = 0;
}
}
};
|
