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

Note: The solution set must not contain duplicate subsets.

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

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

思路

我们之前做过Subsets这一题，我们利用回溯的方法可以取出一个数组所有的Subset。如果Subset里面有重复的元素怎么办呢？非常直接的一种方法就是利用set的数据结构，将结果去重即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    
    public void subset(Set<List<Integer>> result, int index, List<Integer> cur, int[] nums, int layer){
        if(layer == 0){
            result.add(cur);
        }
        else{
            int i = index;
            while(i < nums.length){
                List<Integer> new_cur = new ArrayList<Integer>(cur);
                new_cur.add(nums[i]);
                int new_layer = layer - 1;
                subset(result, i + 1, new_cur, nums, new_layer);
                i++;
            }
        }
    }
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        Arrays.sort(nums);
        for(int i = 0; i <= nums.length; i++){
            List<Integer> cur = new ArrayList<Integer>();
            subset(result, 0, cur, nums, i);
        }
        List<List<Integer>> result_new = new ArrayList<List<Integer>>(result);
        return result_new;
    }
}

当然这个方法可用，但是效率不高。

还有这两种方法，效率和可读性都还不错：

https://discuss.leetcode.com/topic/13543/accepted-10ms-c-solution-use-backtracking-only-10-lines-easy-understand

https://discuss.leetcode.com/topic/22638/very-simple-and-fast-java-solution