组合总和Ⅱ

40. 组合总和 II

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

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

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

示例 1:

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

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

本题的难点在于：集合（数组candidates）有重复元素，但还不能有重复的组合。

我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
• used[i - 1] == false，说明同一树层candidates[i - 1]使用过

为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。

而 used[i - 1] == true，说明是进入下一层递归，取下一个数

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        Arrays.sort(candidates); //根据示例，需要排序
        backtracking(candidates, target, 0, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target , int index, int sum){
        // if(sum>target){
        //     return;
        // }
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = index; i < candidates.length; i++){
            if(sum + candidates[i] > target) continue; //剪枝
            if(i > index && candidates[i] == candidates[i-1] && used[i-1] == false) continue;
            used[i] = true;
            path.add(candidates[i]);
            backtracking(candidates, target, i+1, sum + candidates[i]); 
            used[i] = false;
            path.remove(path.size()-1);
        }
    }

}

• 时间复杂度: $O(n * 2^n)$
• 空间复杂度: $O(n)$

使用 i >index 去重，可以不用used数组，因为只要i大于index必定是同一层的其他数

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); //根据示例，需要排序
        backtracking(candidates, target, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target , int index){
        // if(sum>target){
        //     return;
        // }
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = index; i<candidates.length; i++){
            if(sum + candidates[i] > target) continue; //剪枝
            if(i > index && candidates[i] == candidates[i-1]) continue; //去除重复使用的元素，重复的组合只会出现在同一层
            path.add(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, i+1); 
            sum -= candidates[i];
            path.remove(path.size()-1);
        }
    }