[LeetCode]—Permutations II 求全排列(有重复值)
Permutations II
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]
, and [2,1,1]
.
本题在[LeetCode]—Permutations 求全排列 基础上,出现了重复值元素。
方法一:使用STL next_permutions方法。个人实现版见:[LeetCode]—Next Permutation (全排列字典序)
方法二:依然采用DFS深搜的办法,不过怎么避免重复就是关键问题了。
其实,如果能够保证重复元素的使用先后顺序,就不会出现重复。即当前元素如果有重复,必须等到前面重复元素都被使用了,自己才能使用。
例如:1(1),1(2), 2 括号中标示的是出现的次序。
排列:1(1),1(2),2
1(1),2,1(2)
1(2),1(1),2 X
1(2),2,1(2) X
2,1(1),1(2)
2,1(2),1(1) X
所以,重复元素,保证出现的次序是关键。
代码只需要在[LeetCode]—Permutations 求全排列 基础上多增加一个判断即可。增加28-34行
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
vector<int> cur;
int count;
int n=num.size();
if(n<=1){
res.push_back(num);
return res;
}
sort(num.begin(),num.end());
int *bit=new int[n];
memset(bit,0,sizeof(int)*n);
DFS(res,cur,num,0,bit);
return res;
}
private:
void DFS(vector<vector<int> > &res,vector<int> &cur,vector<int> &num,int count,int *bit){
int n=num.size();
if(count==n){
res.push_back(cur);
return;
}
for(int i=0;i<n;i++){
if(!bit[i]){
int j=i;
while(num[--j]==num[i]){
if(bit[j]==0){ //表示i之前还有未被使用相同元素,出现了重复元素不按序使用的情况
break;
}
}
if(num[j]==num[i])continue; //表示存在重复元素乱序使用;中断该种情况
cur.push_back(num[i]);
bit[i]=1;
DFS(res,cur,num,count+1,bit);
bit[i]=0;
cur.pop_back();
}
}
}
};