90. 子集 II

题目描述

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例：

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

思路

1.这道题和78.子集的解题思路很相似，都是使用回溯法求解。
2.相比较78题，我们需要多进行排序和剪枝操作，排序是为了将相同元素都排列在一起方便剪枝。
3.剪枝的逻辑是，要是当前i>start并且nums[i] == nums[i-1]。因为i>start说明它不是这次回溯操作的第一个元素，若它是重复的，解集中便会出现重复集合。

Java代码实现

public List<List<Integer>> subsetsWithDup(int[] nums) {
        //结果集
        List<List<Integer>> res = new ArrayList<>();
        //当前结果集
        List<Integer> cur = new ArrayList<>();

        //排序
        Arrays.sort(nums);

        for (int i = 0; i <= nums.length; i++) {

            combineWithDup(0,nums,i,cur,res);
        }

        return res;
    }

    private void combineWithDup(int start,int[] nums,int size,List<Integer> cur,List<List<Integer>> res){
        if(start == size){
            res.add(new ArrayList<>(cur));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if(i>start && nums[i]==nums[i-1])
                continue;
            cur.add(nums[i]);
            combineWithDup(i+1,nums,size,cur,res);
            cur.remove(cur.size()-1);
        }
    }