探索组合总和问题（力扣39,40,216）-组合总和II

一、思路

此题与 组合总和I 唯一的区别就在于剪枝优化后的组合总和基础上多个条件：题目给的整数数组是可重复的。

对什么进行去重：在数组可以重复的情况下，并且要求结果中不能出现重复的组合，例如：组合1[1,2,2]，组合2[1,2,2]，这就是两个重复的组合。由于candidates可以存在重复元素，就要对结果进行去重，否则会出现重复的组合，去重是针对当前同一层不能出现重复，而一个组合内不同深度之间是可以出现重复元素的，例如组合[1,1,2]中尽管出现了两个1，但是是candidates不同位置上的1，并没有与其它组合重复。所以要判断所在的层前面相同的元素是否使用过，如果使用过，那么存在的所有情况都可以被包含在前面使用过的元素的组合情况里面，相当于是前面元素的组合情况的一个子集，必定会造成重复，所以直接对出现过的元素进行剪枝操作

二、解题方法

回溯三部曲

1. 递归函数的返回值以及参数：
   先对candidates数组进行排序，创建一个used布尔类型的数组，比上面的 组合总和I 多传入一个use数组

public void backTracking(int[] candidates, int target, int sum,int startIndex,boolean[] used)

2. 回溯函数终止条件：
   终止条件和 组合总和I 相同，略过

3. 单层搜索的过程：
   在for循环横向遍历时，判断同层是否出现过相同的元素，如果出现过，则跳过该循环，继续横向遍历其它元素，判断逻辑为判断当前元素与前一个元素相同，并且不是纵向的元素重复，如果前一个元素used数组为true的话，说明是在相同元素的下一层重复了，而不是横向同层的重复。每当访问过的元素就让该元素对应的used数组置为true，回溯的话就重新为false。

//去重：同层出现重复结点，直接跳过
if(i>0 && candidates[i] == candidates[i-1] && used[i-1] == false) {
   continue;
}
//遍历完之后让used数组为true
used[i] = true;
//回溯为false
used[i] = false;

补充：也可以不使用used标记数组记录是否访问过该元素，startIndex也可以直接进行去重

排序之后的数组，当 i>startIndex 时说明已经不是遍历的同层的第一个结点了，至少从第二个结点开始了，而当此时出现元素和前面一个元素相同的情况的话，也就可以直接去重

三、Code

used标记数组记录

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        boolean[] used = new boolean[candidates.length];
        Arrays.sort(candidates); // 先进行排序
        backTracking(candidates,target,0,0,used);
        return result;
    }

    public void backTracking(int[] candidates, int target, int sum,int startIndex,boolean[] used){
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex;i<candidates.length;i++){
            // 剪枝：如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) {
                break;
            }
            //去重：同层出现重复结点，直接跳过
            if(i>0 && candidates[i] == candidates[i-1] && used[i-1] == false) {
                continue;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            backTracking(candidates,target,sum,i+1,used);
            //回溯
            path.removeLast();
            sum -= candidates[i];
            used[i] = false;
        }
    }
}

startIndex去重

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 先进行排序
        backTracking(candidates,target,0,0);
        return result;
    }

    public void backTracking(int[] candidates, int target, int sum,int startIndex){
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex;i<candidates.length;i++){
            // 剪枝：如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) {
                break;
            }
            //去重：同层出现重复结点，直接跳过
            if(i>startIndex && candidates[i] == candidates[i-1]) {
                continue;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            backTracking(candidates,target,sum,i+1);
            //回溯
            path.removeLast();
            sum -= candidates[i];
        }
    }
}

---