Problem
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]
.Code
void permuteu_r(vector<int> num,vector<int> &result,int l,int n,int pos, vector<vector<int> > &res){ if(pos == n){ res.push_back(vector<int>(result.begin(),result.begin() + pos)); return; } result[pos] = num[l]; permuteu_r(num,result,l + 1,n,pos + 1,res); set<int> processed; processed.insert(num[l]); for(int i = l + 1;i < n;++i){ if(processed.find(num[i]) != processed.end()) continue; swap(num[l],num[i]); result[pos] = num[l]; processed.insert(num[l]); permuteu_r(num,result,l + 1,n,pos + 1,res); } } vector<vector<int> > permuteUnique(vector<int> &num) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<vector<int> > res; int n = num.size(); vector<int> result(n); int count = 0; permuteu_r(num,result,0,n,0,res); return res; }
No comments:
Post a Comment