回溯算法的题目，这样做，秒杀( 三 ) _回溯算法

因为我们要利用Set的特性去重，所以需要加入这个变量Set<List<Integer>> set = new HashSet<>();，另外，为了保证顺序，我们再进行排序Arrays.sort(nums)，这样能避免元素一样，但是顺序不一样的重复子集问题。
所以，结果就出来了。
List<List<Integer>> list = new ArrayList<>(); Set<List<Integer>> set = new HashSet<>(); public List<List<Integer>> subsetsWithDup(int[] nums) { if(nums.length == 0){ return null; } //排序 Arrays.sort(nums); List<Integer> temp = new ArrayList<>(); backTrace(0, nums, temp); return list; } public void backTrace(int start, int[] nums, List<Integer> temp){ //set去重操作 if(!set.contains(temp)){ set.add(new ArrayList<>(temp)); list.add(new ArrayList<>(temp)); } for(int j = start; j < nums.length; j++){ temp.add(nums[j]); backTrace(j+1,nums,temp); temp.remove(temp.size()-1); } }看一下结果发现效率不是很好。

文章插图

那我们再来看一下另外一种剪枝的策略用来去重。

方法二：i > start && nums[i-1] == nums[i]

这种剪枝策略为什么是可以的呢，别急，我来画张图解释一下。

文章插图

所以，我们这种方法就可以做出来了。

    List<List<Integer>> list = new ArrayList<>();    public List<List<Integer>> subsetsWithDup(int[] nums) {        if(nums.length == 0){            return null;        }        Arrays.sort(nums);        List<Integer> temp = new ArrayList<>();        backTrace(0, nums, temp);        return list;    }    public void backTrace(int start, int[] nums, List<Integer> temp){        list.add(new ArrayList<>(temp));                for(int i = start; i < nums.length; i++){            //剪枝策略            if(i > start && nums[i] == nums[i-1]){                continue;            }            temp.add(nums[i]);            backTrace(i+1,nums,temp);            temp.remove(temp.size()-1);        }    }