LeetCode-90. 子集 II-蒲公英云

LeetCode-90. 子集 II

题目来源
90. 子集 II

题目思路

建议先把这两道题做了，在做这道
40.组合总和II
78. 子集
这道题目和78.子集区别就是集合里有重复元素了，而且求取的子集要去重。
那么关于回溯算法中的去重问题，在40.组合总和II和本题是一个套路。
用示例中的[1, 2, 2] 来举例，如图所示：（注意去重需要先对集合排序）
在这里插入图片描述
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

代码实现

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if(nums == null || nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums,0,used);
        return result;
    }
    private void backTracking(int[] nums,int startIndex,boolean[] used){
        result.add(new ArrayList(path));
        if(startIndex == nums.length){
            return;
        }
        for(int i = startIndex;i<nums.length;i++){
            if(i>0 && nums[i] == nums[i-1] && !used[i-1]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backTracking(nums,i+1,used);
            used[i] = false;
            path.remove(path.size()-1);
        }
    }
}