回溯去重问题

第一个题：LC.39

给一个无重复元素的正整数数组candidates和一个正整数target，找出所有和为target的唯一组合，数字可以重复选取

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates,target,0,0,new ArrayList<>());
        return res;
    }
​
    public void backtrack(int[] candidates,int target,int index,int sum,List<Integer> list){
        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = index; i < candidates.length; i++){
            //if(i > 0 && candidates[i] == candidates[i-1]) continue;
            if(sum + candidates[i] > target) break;
            list.add(candidates[i]);
            backtrack(candidates,target,i,sum + candidates[i],list);
            list.remove(list.size() - 1);
        }
    }
}

这个题，题目当中说无重复元素，每个数可以无限取，所以不存在去重的问题，注释的那一行可以去掉了

看下一个需要去重的题目：

第二个题：LC.40

题目和LC.39一样，唯一不同的条件是给的数组candidates含有重复元素。这个时候就需要去重了

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates,target,0,0,new ArrayList<>());
        return res;
    }
​
    public void backtrack(int[] candidates,int target,int index,int sum,List<Integer> list){
        if(target == sum){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = index; i < candidates.length; i++){
            //在同一个for循环中，正在选当前层的元素
            //i >= index 的部分才是这一层可以选的元素，而不是i > 0的部分
            //同一层的元素不能重复而已
            if(i > index && candidates[i] == candidates[i-1]) continue;
            if(sum + candidates[i] > target) break;
            list.add(candidates[i]);
            backtrack(candidates,target,i+1,sum + candidates[i],list);
            list.remove(list.size() - 1);
        }
    }
}

什么时候需要去重呢？

假设来到第一次循环，候选数组为：[1,2,3,3,4,5,6]

我们来到第一次选择，这个时候可以选的数字有1，2，3，3，4，5，6

注意在这一轮中，选择第一个3和第二个3，实际上是一样的，所以这里需要去重

怎么去重？

每一次调用回溯方法backtrack()，实际上就是进入了一轮选择

在这一轮选择中，我们的起始位置是index

那么在[index + 1 , nums.length - 1]这个区间内，重复的数字都要去掉

就有了下面这一行判断

这一行代表同一轮选择中的情况

if(i > index && candidates[i] == candidates[i-1]) continue;

第三个题：LC.46

给一个不含重复数字的整数数组nums，返回其所有可能的全排列

这个题加上一个boolean数组来判断是否选过该数字就可以了，因为数组没有重复数字

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        res = new ArrayList<>();
        boolean[] isVisited = new boolean[n];
        backtrack(nums,isVisited,0,n,new ArrayList<>());
        return res;
    }
​
    public void backtrack(int[] nums,boolean[] isVisited,int count,int n,List<Integer> list){
        if(count == n){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(!isVisited[i]){
                list.add(nums[i]);
                isVisited[i] = true;
                backtrack(nums,isVisited,count+1,n,list);
                isVisited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

第四个题：LC.47

和第三题类似，唯一的区别就是数组中存在重复的数字

什么时候会出现重复组合的情况？

也是在同一轮次中，选择了相同的数字，就会造成重复

怎么判断是否是相同轮次中？

因为我们用到的是boolean数组来判断是否使用过这个数字

那么，之前选择过的数字，isVisited[i]都变成了true

现在没有选择过的数字，isVisited[i]就是false

如果当前数字和前一个数字相同，并且前一个数字并没有被选取，说明他们处在同一轮选择的情况，要跳过

if(i > 0 && nums[i] == nums[i-1] && !isVisited[i-1]) continue;

 

题目代码：

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permuteUnique(int[] nums) {
        res = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(nums,new boolean[nums.length],0,new ArrayList<>());
        return res;
    }
​
    public void backtrack(int[] nums,boolean[] isVisited,int count,List<Integer> list){
        if(count == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
​
        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i-1] && !isVisited[i-1]) continue;
            if(!isVisited[i]){
                list.add(nums[i]);
                isVisited[i] = true;
                backtrack(nums,isVisited,count+1,list);
                isVisited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

总的来说，什么时候应该去重？

同一轮次中出现重复数字的情况就应该去重

对于总和组合和排列组合来说，同一轮次的情况是不同的

总和组合的同一轮次，是[index , nums.length - 1]这个区间上

而排列组合，同一轮次是isVisited[i]为false的数字