问题

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合
candidates 中的数字可以无限制重复被选取

说明：
所有数字（包括 target）都是正整数
解集不能包含重复的组合

示例 1：
输入：candidates = [2,3,6,7], target = 7
所求解集为：
[
[7],
[2,2,3]
]

示例 2：
输入：candidates = [2,3,5], target = 8
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]

思路

leetcode-39：求组合总和 - 图1
因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回

回溯三部曲

  • 递归函数参数
    • 这里依然是定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。（这两个变量可以作为函数参数传入）
    • 首先是题目中给出的参数，集合candidates，和目标值target
    • 此外我还定义了int型的sum变量来统计单一结果path里的总和，其实这个sum也可以不用，用target做相应的减法就可以了，最后如果target==0就说明找到符合的结果了，但为了代码逻辑清晰，依然用了sum

本题还需要**startIndex**来控制**for**循环的起始位置，对于组合问题，什么时候需要**startIndex**呢？

  • 如果是一个集合来求组合的话，就需要startIndex，例如：leetcode-77：组合
  • 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：leetcode-17：电话号码的字母组合

    注意以上只是说求组合的情况，如果是排列问题，又是另一套分析的套路

  1. List<List<Integer>> result = new ArrayList<List<Integer>>();
  2. List<Integer> path = new ArrayList<Integer>();
  3. public void backtracking(int[] candidates, int target, int sum, int startIndex)
  • 递归终止条件

在如下树形结构中：
leetcode-39：求组合总和 - 图2
从叶子节点可以清晰看到，终止只有两种情况

  • sum大于target

  • sum等于target

    1. if (sum > target) {
    2.   return;
    3. }
    4. if (sum == target) {
    5.   result.add(new ArrayList<Integer>(path));
    6.   return;
    7. }

  • 单层搜索的逻辑

    • 单层for循环依然是从startIndex开始，搜索candidates集合

      1. for (int i = startIndex; i < candidates.length; i++) {
      2. sum += candidates[i];
      3. path.add(candidates[i]);
      4. backtracking(candidates, target, sum, i); // 关键点:不用i+1了，表示可以重复读取当前的数
      5. sum -= candidates[i];   // 回溯
      6. path.remove(path.size() - 1);        // 回溯
      7. }
      1. class Solution {
      2. List<List<Integer>> result = new ArrayList<List<Integer>>();
      3. List<Integer> path = new ArrayList<Integer>();
      5. public void backtracking(int[] candidates, int target, int sum, int startIndex) {
      6.    if (sum > target) {
      7.        return;
      8.    }
      10.    if (sum == target) {
      11.        result.add(new ArrayList<Integer>(path));
      12.        return;
      13.    }
      15.    for (int i = startIndex; i < candidates.length; i++) {
      16.        sum += candidates[i];
      17.        path.add(candidates[i]);
      18.        backtracking(candidates, target, sum, i); 
      19.        sum -= candidates[i];   
      20.        path.remove(path.size() - 1);        
      21.    }
      22. }
      24. public List<List<Integer>> combinationSum(int[] candidates, int target) {
      25.    backtracking(candidates, target, 0, 0);
      26.    return result;
      27. }
      28. }


      剪枝优化

      在这个树形结构中：
      leetcode-39：求组合总和 - 图3
      以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回
      其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了
      那么可以在for循环的搜索范围上做做文章了

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

如图：
leetcode-39：求组合总和 - 图4
for循环剪枝代码如下：

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