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].

C++:
01 void swap(vector<int>& num, int a, int b)
02 {
03     int tmp=num[a];
04     num[a]=num[b];
05     num[b]=tmp;
06 }
07 
08 void permutation(vector<vector<int> >& result,
09                  vector<int>& num, int p, int q)
10 {
11     if(p==q){
12         result.push_back(num);
13         return;
14     }else{
15         set<int> table;
16         for(int i=p;i<=q;i++){
17             if(table.find(num[i])==table.end()){
18                 table.insert(num[i]);
19                 swap(num,p,i);
20                 permutation(result,num,p+1,q);
21                 swap(num,p,i);
22             }
23         }
24     }
25 }
26 
27 vector<vector<int> > permuteUnique(vector<int> &num)
28 {
29       int n=num.size();
30       vector<vector<int> > result;
31       if(n==0)
32           return result;
33       int start=0;
34       int end=n1;
35       permutation(result, num, start, end);
36       return result;
37 }
Advertisements
This entry was posted in Array and linked list, Recursive. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s