Subsets II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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],
  []
 ]

代码：

 class Solution {  
 public:  
   //Version 1: 从树状结构考虑递归方法  
   vector<vector<int> > subsetsWithDup(vector<int> &S) {  
     vector<vector<int> > result;  
     if (S.empty()) return result;  
     sort(S.begin(), S.end());  
     vector<int> oneset;  
     subsetsWithDupHelper(S, 0, oneset, result);  
     return result;  
   }  
   
   void subsetsWithDupHelper(vector<int> &S, int start, vector<int> &oneset, vector<vector<int> > &result) {  
     result.push_back(oneset);  
     for (int i = start; i < S.size(); ++i) {  
       if (i != start && S[i] == S[i - 1]) {  
         continue;  
       }    
       oneset.push_back(S[i]);  
       subsetsWithDupHelper(S, i + 1, oneset, result);  
       oneset.pop_back();  
     }  
   }   
 };  
   
 // {}  
 // 1  
 // 2  
 // 1,2  
 // 2,2  
 // 1,2,2  
 class Solution {  
 public:  
   vector<vector<int> > subsetsWithDup(vector<int> &S) {  
     sort(S.begin(), S.end());  
     vector<vector<int>> ret = {{}};  
     int size = 0, startIndex = 0;  
     for (int i = 0; i < S.size(); i++) {  
       startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;  
       size = ret.size();  
       for (int j = startIndex; j < size; j++) {  
         vector<int> temp = ret[j];  
         temp.push_back(S[i]);  
         ret.push_back(temp);  
       }  
     }  
     return ret;  
   }  
 };