47. Permutations II
Description
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Analysis
这道题是Permutations I的加强版，给出的序列中可能存在一些重复的元素，导致全排列中会出现一些重复的项目。
所以需要从简单的情况考虑，假如序列为[1,1,1,1]`，如果四个1代表不同的意义，则有
4!
种情况。但此题并不需要我们考虑顺序，即所有元素都代表相同的意义，所以实际上只有1种情况。
那么就需要给每个元素打上一个标签，给出一个布尔数组， 用两个布尔值来标记每个元素的状态。
考虑两种特殊情况:
1.如果当前元素已经被使用过，则在当前循环中应该被跳过
2.如果当前元素在之前出现过，且前一个元素还没有被使用过，则也应当被跳过。
第一种情况较好理解，但第二种就比较晦涩了。其实，第二种情况是为了保证相同元素之间的有序性。依然考虑边界条件[1,1,1,1]，如果当前元素为第二个1，但第一个1还没有被使用过，则应该跳过当前这个2，来保证是按顺序插入元素。
总结一下就是: 1.首先保证给定向量中元素的有序性（以便判断是否出现了重复元素）
2.对于需要跳过的元素，其判断依据为:
如果该元素已被使用，跳过 如果该元素为重复元素且前一元素还未被使用过，跳过
代码如下:
code
class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & templist,vector<int> & nums,bool * used){
if(templist.size()==nums.size()){
res.push_back(templist);
return;
}
for(int i=0;i<nums.size();++i){
if(used[i]||i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;
used[i]=true;
templist.push_back(nums[i]);
backtracking(res,templist,nums,used);
used[i]=false;
templist.pop_back();
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
bool used[nums.size()]={false};
vector<vector<int>> res;
vector<int> templist;
sort(nums.begin(),nums.end());
backtracking(res,templist,nums,used);
return res;
}
};