Subsets

Given a set of distinct integers, 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,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [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,
08             vector<vector<int> >& result, vector<int> cur)
09 {
10     if(index==size){
11         result.push_back(cur);
12         return;
13     }
14     subset(A,size,index+1,result,cur);
15     cur.push_back(A[index]);
16     subset(A,size,index+1,result,cur);
17 }
18 
19 vector<vector<int> > subsets(vector<int> &S) {
20     vector<vector<int> > result;
21     int n=S.size();
22     if(n==0)
23         return result;
24     int* A=new int[n];
25     for(int i=0;i<n;i++)
26         A[i]=S[i];
27     qsort(A,n,sizeof(int),compare);
28     vector<int> cur;
29     subset(A,n,0,result,cur);
30     return result;
31 }
Advertisements
This entry was posted in Recursive, String. 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