Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

 

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
C++:
01 #include <algorithm>
02 int compare(const void* a, const void* b)
03 {
04     return (*(int*)a-*(int*)b);
05 }
06 
07 void subset(int A[], int size, int index,
            vector<vector<int> >& result, vector<int> cur)
08 {
09     if(index==size){
10         result.push_back(cur);
11         return;
12     }
13     int t=1;
14     while((index+t<size)&&(A[index+t]==A[index+t1]))
15         t++;
16     subset(A,size,index+t,result,cur);
17     cur.push_back(A[index]);
18     subset(A,size,index+1,result,cur);
19 }
20 
21 vector<vector<int> > subsetsWithDup(vector<int> &S) {
22       vector<vector<int> > result;
23       int n=S.size();
24       if(n==0)
25           return result;
26       int* A=new int[n];
27       for(int i=0;i<n;i++)
28           A[i]=S[i];
29       qsort(A,n,sizeof(int),compare);
30       vector<int> cur;
31       subset(A,n,0,result,cur);
32       return result;
33 }
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