描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

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

示例

示例 1:

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

示例 2:

  1. 输入: candidates = [2,5,2,1,2], target = 5,
  2. 输出:
  3. [
  4. [1,2,2],
  5. [5]
  6. ]

提示

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

解题思路

回溯算法 + 剪枝（Java、Python）

这道题的难点是 如何去重，题解的做法是先对数组排序，相同元素只对第一个递归，其余元素直接剪枝。证明如下：

剪枝发生在：同一层数值相同的结点第 2、3 … 个结点，因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果，同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 1 个结点更多，并且是第 1 个结点的子集。

1599718525-iXEiiy-image.png

代码

class Solution {
    List<Integer> path = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);  // 关键步骤
        dfs(0, target, candidates);
        return ans;
    }
    public void dfs(int cur, int target, int[] candidates) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = cur; i < candidates.length; i++) {
            if (candidates[i] > target) { // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
                break;
            }
            if (i > cur && candidates[i] == candidates[i - 1]) { // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
                continue;
            }
            path.add(candidates[i]);
            dfs(i + 1, target - candidates[i], candidates);
            path.remove(path.size() - 1);
        }
    }
}