LeetCode OJ：Subsets II（子集II）

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

例子：

If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

求子集而已，不过这里的麻烦是子集的数字可能是重复的，这样可能会出现相同的结果的情况，解决的方法是先排序，然后dfs，dfs的时候如果发现当前的数与前一个数相等的话那么跳过进行下一个。这样就不会出现相同的vector的情况，具体代码如下：

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
 4           ret.clear();
 5           tmp.clear();
 6           rawVec = nums;
 7           sort(rawVec.begin(), rawVec.end());
 8           dfs(0);
 9           return ret;
10     }
11 
12     void dfs(int start)
13     {
14         ret.push_back(tmp); //首先push一个空集
15         for(int i = start; i < rawVec.size(); ++i){
16             if(i != start && rawVec[i] == rawVec[i - 1]) continue;  //这里的i != start；应该注意
17             tmp.push_back(rawVec[i]);
18             dfs(i + 1);
19             tmp.pop_back();
20         }
21     }
22 private:
23     vector<vector<int>> ret;
24     vector<int> tmp;
25     vector<int> rawVec;
26 
27 };

下面是java代码，改成了没有全局变量的形式，比上面的看起来要简单一些，代码如下所示，方法和上面的也有些许的不同：

 1 public class Solution {
 2     public List<List<Integer>> subsetsWithDup(int[] nums) {
 3         Arrays.sort(nums);
 4         List<List<Integer>> ret = new ArrayList<List<Integer>>();
 5         List<Integer> tmp = new ArrayList<Integer>();    
 6         dfs(ret, tmp, nums, 0, nums.length);
 7         return ret;
 8     }
 9     
10     public void dfs(List<List<Integer>> ret, List<Integer> tmp, int [] nums, int start, int limit){
11         if(start > limit)
12             return;
13         else if(start == limit){
14             ret.add(new ArrayList<Integer>(tmp));
15             return;
16         }else{
17             ret.add(new ArrayList<Integer>(tmp));
18             for(int i = start; i < limit; ++i){
19                 tmp.add(nums[i]);
20                 dfs(ret, tmp, nums, i+1, limit);
21                 tmp.remove((Integer)nums[i]);
22                 while(i+1 < limit && nums[i+1] == nums[i]) //跳过所有的重复的数字
23                     i++; //这里加完了之后while循环又会再加一次，正好跳过所有的重复的值
24             }
25         }
26     }
27 }