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 void subsetsWithDupHelper(vector<vector<int>>& result,
02                       map<int, int>& A, map<int, int>::iterator p, vector<int> current)
03 {
04     if(p==A.end())
05     {
06         result.push_back(current);
07         return;
08     }
09     int num=p->first;
10     int count=p->second;
11     p++;
12     for(int i=0;i<=count;i++)
13     {
14         subsetsWithDupHelper(result,A,p,current);
15         current.push_back(num);
16     }
17 }
18 class Solution {
19 public:
20     vector<vector<int> > subsetsWithDup(vector<int> &S) {
21         // Start typing your C/C++ solution below
22         // DO NOT write int main() function
23         map<int, int> A;
24         vector<vector<int>> result;
25         for(int i=0;i<S.size();i++)
26         {
27             if(A.find(S[i])==A.end())
28             {
29                 A[S[i]]=1;
30             }
31             else
32             {
33                 A[S[i]]++;
34             }
35         }
36         map<int, int>::iterator it=A.begin();
37         vector<int> tmp;
38         subsetsWithDupHelper(result, A, it, tmp);
39         return result;
40     }
41 };
Advertisements
This entry was posted in Hashtable and Map, 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