LeetCode90. 子集 II

方法一：

        本题和上一题的子集问题最大的不同就是有重复的数字，就需要去重。和之前的去重的一样的就是要先排序然后把结果用set保存。

方法二：

        用Boolean数组来解决，如果同一个树枝使用过是true，如果是同一个树层使用是false。

用set处理

class Solution {
    List path = new ArrayList<>();
    Set> res = new HashSet<>();
    public List> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        back(nums,0);
        return new ArrayList(res);
    }
    public void back(int[] nums,int startIndex){
        res.add(new ArrayList(path));
        if(path.size()>=nums.length){
            return;
        }
        for(int i = startIndex;i 
方法二：用boolean数组处理
 
class Solution {
    List path = new ArrayList<>();
    List> res = new ArrayList<>();
    boolean[] used;
    public List> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        back(nums,0);
        return res;
    }
    public void back(int[] nums,int startIndex){
        res.add(new ArrayList(path));
        
        if(path.size()>=nums.length){
            return;
        }
        for(int i = startIndex;i0 && nums[i] == nums[i-1] && used[i-1] == false){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            back(nums,i+1);//说明同一树枝使用过
            path.remove(path.size()-1);
            used[i] = false;//说明同一树层使用过
        }
    }
}