题目

力扣题目链接

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

思路

题目中的无限制重复被选取，吓得我赶紧想想 出现0 可咋办，然后看到下面提示：1 <= candidates[i] <= 200，我就放心了。

本题和 77.组合、216.组合总和III 的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

本题搜索的过程抽象成树形结构如下：
image.png
注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回。

而在 77.组合、216.组合总和III 中都可以知道要递归 K 层，因为要取 k 个元素的组合。

因为题目要求解集不能包含重复的组合，所以还需要 startIndex 来控制 for 循环的起始位置。

题目规定 candidates 中的数字可以无限制重复被选取，因此在递归调用 backtracking 时，i 就不用 +1 了，表示可以重复选择当前数字：

  1. for (int i = startIndex; i < candidates.length; i++) {
  2.     path.add(candidates[i]);
  3.     sum += candidates[i];
  5.     // 关键点:不用i+1了，表示可以重复读取当前的数
  6.     backtracking(i);
  8.     path.removeLast();
  9.     sum -= candidates[i];
  10. }

那么，我们可以得出第一版的代码：

  1. class Solution {
  2.     int[] candidates = null;
  3.     int target = 0;
  5.     List<List<Integer>> result = new ArrayList<>();
  6.     LinkedList<Integer> path = new LinkedList<>();
  8.     // 定义 int 型的 sum 变量来统计单一结果 path 里元素的总和
  9.     int sum = 0;
  11.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  12.         this.candidates = candidates;
  13.         this.target = target;
  14.         backtracking(0);
  15.         return result;
  16.     }
  18.     void backtracking(int startIndex) {
  19.         // 终止条件
  20.         if (sum > target) {
  21.             return;
  22.         }
  23.         // 符合题目要求，收集答案
  24.         if (sum == target) {
  25.             result.add(new ArrayList<>(path));
  26.             return;
  27.         }
  29.         for (int i = startIndex; i < candidates.length; i++) {
  30.             path.add(candidates[i]);
  31.             sum += candidates[i];
  33.             // 关键点:不用i+1了，表示可以重复读取当前的数
  34.             backtracking(i);
  36.             path.removeLast();
  37.             sum -= candidates[i];
  38.         }
  39.     }
  40. }

剪枝

在这个树形结构中：
image.png
以及上面的版本一的代码大家可以看到，对于 sum 已经大于 target 的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断 sum > target 的话就返回。

其实如果已经知道下一层的 sum 会大于 target ，就没有必要进入下一层递归了。

那么可以在 for 循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的 sum（就是本层的 sum + candidates[i] ）已经大于 target ，就可以结束本轮 for 循环的遍历。

如图：
image.png

for 循环剪枝代码如下：

  1. for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {

本题的剪枝优化，这个优化如果是初学者的话并不容易想到。在求和问题中，排序之后加剪枝是常见的套路。

答案

class Solution {
    int[] candidates = null;
    int target = 0;

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

    // 定义 int 型的 sum 变量来统计单一结果 path 里元素的总和
    int sum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 对集合做排序
        Arrays.sort(candidates);

        this.candidates = candidates;
        this.target = target;

        backtracking(0);
        return result;
    }

    void backtracking(int startIndex) {
        // 终止条件
        // 符合题目要求，收集答案
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 如果 sum + candidates[i] > target 就提前终止遍历
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            path.add(candidates[i]);
            sum += candidates[i];

            // 关键点:不用i+1了，表示可以重复读取当前的数
            backtracking(i);

            path.removeLast();
            sum -= candidates[i];
        }
    }
}

REF

https://programmercarl.com/0039.组合总和.html
https://leetcode-cn.com/problems/combination-sum/