组合 - leetcode-216：组合问题Ⅲ - 《算法珠玑》

问题
回溯三部曲
剪枝

问题

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字

说明：

所有数字都是正整数
解集不能包含重复的组合

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

回溯三部曲

确定递归函数参数和返回值
- 需要一维数组path来存放符合条件的结果，二维数组result来存放结果集，依然定义path和result为全局变量
```
List<List<Integer>> result = new ArrayList<List<Integer>>(); // 存放结果集 
List<Integer> path = new ArrayList<Integer>(); // 符合条件的结果
```
- 接下来还需要如下参数：
  - targetSum(int)目标和，也就是题目中的n
  - k(int)就是题目中要求k个数的集合
  - sum(int)为已经收集的元素的总和，也就是path里元素的总和
  - startIndex(int)为下一层for循环搜索的起始位置
```
List<List<Integer>> result = new ArrayList<List<Integer>>(); 
List<Integer> path = new ArrayList<Integer>();
void backtracking(int targetSum, int k, int sum, int startIndex)
```
    其实这里sum这个参数也可以省略，每次targetSum减去选取的元素数值，然后判断如果targetSum为0了，说明收集到符合条件的结果了
    还要强调一下，回溯法中递归函数参数很难一次性确定下来，一般先写逻辑，需要啥参数了，填什么参数
确定终止条件
- 在上面已经说了，k其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义，所以如果path.size()和 k相等了，就终止
- 如果此时path里收集到的元素和（sum）和targetSum（就是题目描述的n）相同了，就用result收集当前的结果
```
if (path.size() == k) {
if (sum == targetSum) 
   result.add(new ArrayList<Integer>(path));
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
```
单层搜索过程

leetcode-216：组合问题Ⅲ - 图1
处理过程就是path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和

for (int i = startIndex; i <= 9; i++) {
    sum += i;
    path.add(i);
    backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
    sum -= i; // 回溯 
    path.remove(i); // 回溯 
}

别忘了处理过程和回溯过程是一一对应的，处理有加，回溯就要有减！

class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public void backtracking(int k, int targetSum, int sum, int startIndex) {
        if (path.size() == k) {
            if (sum == targetSum) 
                result.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i; 
            path.add(i); 
            backtracking(k, targetSum, sum, i + 1); 
            sum -= i; 
            path.remove(i); 
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 0, 1);
        return result;
    }
}

剪枝

leetcode-216：组合问题Ⅲ - 图2
已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。那么剪枝的地方一定是在递归终止的地方剪

class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public void backtracking(int k, int targetSum, int sum, int startIndex) {
        if(sum > targetSum){
            return;  //剪枝
        }
        if (path.size() == k) {
            if (sum == targetSum) 
                result.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i; 
            path.add(i); 
            backtracking(k, targetSum, sum, i + 1); 
            sum -= i; 
            path.remove(i); 
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 0, 1);
        return result;
    }
}