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 void subsetsHelper(vector<vector<int>>& result, vector<int>& S,
02                    vector<int>& current, int p)
03 {
04     int n=S.size();
05     if(p>=n)
06     {
07         result.push_back(current);
08         return;
09     }
10     current.push_back(S[p]);
11     subsetsHelper(result,S,current,p+1);
12     current.pop_back();
13     subsetsHelper(result,S,current,p+1);
14 }
15 class Solution {
16 public:
17     vector<vector<int> > subsets(vector<int> &S) {
18         // Start typing your C/C++ solution below
19         // DO NOT write int main() function
20         for(int i=1;i<S.size();i++)
21         {
22             int k=S[i];
23             int j=i1;
24             for(;j>=0;j)
25             {
26                 if(S[j]>k)
27                 {
28                     S[j+1]=S[j];
29                 }
30                 else
31                  break;
32             }
33             S[j+1]=k;
34         }
35         vector<vector<int>> result;
36         vector<int> current;
37         subsetsHelper(result,S,current,0);
38         return result;
39     }
40 };
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