leetcode_40.组合总和 II

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

去重思路:

1. 排序数组： 在开始搜索之前，将候选数组进行排序。排序后，相同的数字会相邻排列。

2. 剪枝操作： 在搜索过程中，通过剪枝操作来避免产生重复的组合。具体来说，在每次选择数字时，通过判断当前数字是否与前一个数字相同，并且前一个数字没有被使用过，如果满足这两个条件，就跳过当前数字，避免了产生重复的组合。

回溯的思路：

1. 选择：在每一步中，选择当前可用的候选数字中的一个，将其添加到当前的组合中。

2. 约束条件：循环遍历从当前索引 index 开始的所有元素，需要检查当前组合的和是否超过了目标值，如果超过了，则放弃这个选择，因为这个组合无法达到目标。

3. 目标：当当前组合的和正好等于目标值时，将当前组合加入结果集。

4. 回溯：如果当前选择导致了组合和超过了目标值，或者已经遍历完了所有的候选数字，需要回溯到之前的状态，尝试其他的选择。同时，还要确保在回溯的过程中撤销当前选择（将当前元素从临时列表 temp 中移除，并将其标记为未使用），以便进行下一次尝试。

class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        dfs(candidates, target, 0, used);
        return ans;
    }

    public void dfs(int[] candidates, int target, int index, boolean[] used) {
        if (target == 0) {
            ans.add(new LinkedList<>(temp));
            return;
        }
        if (index == candidates.length) return;
        for (int i = index; i < candidates.length; i++) {
            if (target - candidates[i] < 0) return;
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;

            temp.add(candidates[i]);
            used[i] = true;
            dfs(candidates, target - candidates[i], i + 1, used);
            temp.remove(temp.size() - 1);
            used[i]=false;
        }
    }
}