组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

方法：回溯

算法思路：

与39.组合总和不同的是，本题candidates的元素是有重复的，每个数字在每个组合中只能使用一次。所以，我们需要对同一树层上使用过的元素去重，同一树枝上的不需要去重。

  1. 确定递归函数参数

    除39.组合总和设置的参数外，还需加一个boolean型数组used，用来记录同一树层上的元素是否使用过。

  2. 确定递归终止条件

    当sum大于等于target时终止递归，当sum等于target时，将path添加到result中。剪枝优化可参考39.组合总和，先将candidates数组排序，当sum + candidates[i] > target时，后续的数就不需要遍历了，直接break。

  3. 单层搜索的过程

    for循环从startIndex开始，搜索candidates数组，若遇到重复的，则直接continue跳过。

    if(i > startIndex && candidates[i] == candidates[i - 1]){
                    continue;
                }

代码实现：

class Solution {
    public List<List<Integer>> result = new ArrayList<>();
    public LinkedList<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++){
            if(sum + candidates[i] > target){
                break;
            }
            if(i > startIndex && candidates[i] == candidates[i - 1]){
                continue;
            }
            sum += candidates[i];
            path.add(candidates[i]);
            backTracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

参考

代码随想录 - 组合总和II