题目

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],
  []
]

方法

利用DFS，一层相同的元素不要放入即可。

    public void getSets(int[] S, int start, int end, List<List<Integer>> list, List<Integer> subList) {
        list.add(subList);
        int pre = Integer.MIN_VALUE;
        for (int i = start; i < end; i++) {
            List<Integer> newSubList = new ArrayList<Integer>(subList);
            int cur = S[i];
            if (pre != cur) {
                newSubList.add(S[i]);
                getSets(S, i + 1, end, list, newSubList);
                pre = cur;
            } 

        }
    }
    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        List<Integer> subList = new ArrayList<Integer>();
        getSets(num, 0, num.length, list, subList);
        return list;
    }