subset I & II

subset I & II

I a little trouble

I use O(n) extra space to mark whether each element is used to get ride of duplicates. This time, I add some conditions in DFS to save those spaces.

  • First check whether result is empty. If it is empty , push current elemt to t.
  • Second, if result is not empty, check whether t(saving current one result) is empty. If t is empty and current element is not same as the first element in the last vector of result. push it into t.
  • If t is not empty, but current element is not same as the last element in t, push it into t.
 1 class Solution {
 2 private:
 3     vector< vector< int > > result;
 4 public:
 5     vector<vector<int> > subsets(vector<int> &S) {
 6         result.clear();
 7         vector< int > t;
 8         t.clear();
 9         result.push_back(t);
10         int n = S.size();
11         if ( 0 == n ) {
12             return result;
13         }
14         sort(S.begin(),S.end());
15         for ( int i = 1; i <= n; i++  ) {
16             t.clear();
17             DFS(S,t,0,i);
18         }
19         return result;
20     }
21     void DFS( vector< int > &s, vector< int >& t, int start, int len ) {
22         if ( 0 == len ) {
23             result.push_back(t);
24             return;
25         }
26         for ( int i = start; i < s.size(); i++ ) {
27             if ( ( 1 == result.size() ) || ( 0 == t.size() && s[i] != result[result.size()-1][0] )  || ( s[i] != t[t.size()-1] ) ) {
28                 t.push_back(s[i]);
29                 DFS(s,t,i+1,len-1);
30                 t.pop_back();
31             }
32         }
33     }
34 };

II a little more trouble

A good understanding of DFS can resolve this problem. Assuming that we generate the result from length 1 to the sizeof S.

len = 1We go throgh s, enumerate the first element. The first element must be chosen. After that, the next first element must not same as the before one. Because the length now is 1, and if they are the same, they become duplicate result.

len = 2We need to chose the first element using the same way, then the second element.

 1 class Solution {
 2 private:
 3     vector< vector< int > > result;
 4 public:
 5     vector<vector<int> > subsetsWithDup(vector<int> &S) {
 6         int n = S.size();
 7         result.clear();
 8         vector< int > t;
 9         t.clear();
10         result.push_back(t);
11         if ( 0 == n ) {
12             return result;
13         }
14         sort(S.begin(),S.end());
15         for( int i = 1; i <= n; i++ ) {
16             t.clear();
17             DFS(S,t,0,i);
18         }
19         return result;
20     }
21     void DFS( vector< int >& s, vector< int >&t, int start, int len ) {
22         if ( 0 == len ) {
23             result.push_back(t);
24             return;
25         }
26         for ( int i = start; i < s.size(); i++ ) {
27             if ( ( start == i ) || ( s[i] != s[i-1] ) ) {
28                 t.push_back(s[i]);
29                 DFS(s,t,i+1,len-1);
30                 t.pop_back();
31             }
32         }
33     }
34 };

Loading Disqus comments...
Table of Contents