Sunday, January 6, 2013

[LeetCode] 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],
  []
]
» Solve this problem


[解题思路]
跟Subset I思路一样,http://fisherlei.blogspot.com/2013/01/leetcode-subsets.html。 区别只在于去重。
代码的区别只有Line 24, 25。对于当前字符,如果下一个字符与之相等,则过滤掉。

[Code]
1:    vector<vector<int> > subsetsWithDup(vector<int> &S) {  
2:      // Start typing your C/C++ solution below    
3:      // DO NOT write int main() function  
4:      vector<vector<int> > result;  
5:      vector<int> output;   
6:      if(S.size() ==0) return result;  
7:      result.push_back(output);  
8:      sort(S.begin(), S.end());  
9:      generateSub(S, 0, result, output);  
10:    }  
11:    void generateSub(  
12:      vector<int> &s,   
13:      int step,   
14:      vector<vector<int> > &result,  
15:      vector<int>& output)  
16:    {         
17:      for(int i = step;i<s.size(); i++ )  
18:      {  
19:        output.push_back(s[i]);  
20:        result.push_back(output);  
21:        if(i< s.size()-1)  
22:          generateSub(s, i+1, result, output);  
23:        output.pop_back();  
24:        while(i<s.size()-1 && s[i] == s[i+1])  
25:          i++;  
26:      }      
27:    }  


No comments: