LeetCode 90：子集 II

链接
题目：

思路：回溯（元素可重不可复选）

与子集不同的是题目给的元素有重复，如果按之前的做法会导致答案有重复：

这里需要添加选择时的条件以修剪节点！
①有重复元素就要先排序 ！，让相同的元素靠在⼀起，
②如果发现 nums[i] == nums[i-1] 则跳过 ！ 同时 i>start

Java实现：

class Solution {
    
    List<List<Integer>> res=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
    
        Arrays.sort(nums);
        dfs(nums,0);
        return res;
    }

    void dfs(int[] nums,int start){
    
        res.add(new LinkedList(path));
        for(int i=start;i<nums.length;i++){
    
            //做选择
            //修剪，值相同的相邻节点只遍历一次
            if(i>start && nums[i]==nums[i-1]){
     // i>start !
                continue;
            }
            path.add(nums[i]);
            dfs(nums,i+1);
            //撤销
            path.removeLast();
        }
    }
}

注意 ：i >start !