题目描述
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
解题思想
因为存在去重操作,因此要注重树层上的去重操作
全排列的树层去重操作
if(i>0 && nums[i] ==nums[i-1] &&used[i-1]==false) //树层去重
continue;
组合的树层去重操作
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
continue;
或
if (i > startIndex && candidates[i] == candidates[i - 1])
continue;
代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backTracking(vector<int>& nums, vector<bool>used) {
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(i>0 && nums[i] ==nums[i-1] &&used[i-1]==false) //树层去重
continue;
if(used[i]==true) continue; //在树枝上避免重复使用
used[i]=true;
path.push_back(nums[i]);
backTracking(nums,used);
used[i]=false;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backTracking(nums, used);
return res;
}
};