7.2组合总和（LC216-M）

算法：

以k=2,n=4为例，画树形结构：

k控制着树的深度

宽度由1-9控制

回溯三部曲：

1.确定返回值和参数：

返回值：void

参数：

targetsum，目标和，即n

k

sum，当前组合的和，要和n比较

startindex:控制当前递归层，从哪个数开始取数

2.确定终止条件：

path.size()==k时，没必要往下递归了

结果在叶子节点中，若在叶子结点中发现：targetsum == sum，就把该符合条件的结果放进结果集

3.单层递归逻辑

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

为什么递归时是i+1：

为什么要这样回溯：

剪枝：

从n的角度剪枝：

若sum>targetsum，则没有必要继续递归了

从k的角度剪枝：

比如k=5,n=100

按照之前的想法，到9的时候，后面剩下的元素为0个，根本不可能凑到5个数来组合。无法满足集合个数。

在for循环中，对i的边界进行控制。

调试过程（用了剪枝优化）：

class Solution {
    //全局变量
    //path result
    List<List<Integer>> result = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
//在 backTracking 函数中，sum 的初始值为 0，这是因为我们在寻找组合数时需要从零开始累加元素，直到达到目标和。
        backtracking (k, n, 0,1);
        return result;

    }
    void backtracking (int k, int n, int sum, int startindex){
        //从n剪枝
        if (sum > n) return;
        //确定终止条件
        if (path.size()==k) {
            if (sum == n) {
                result.add(new LinkedList<>(path));
            }
            return;
        }
        //单层递归逻辑(要从k剪枝)
        for (int i=startindex; i<=9-(k-path.size())+1; i++) {
            sum += i;
            backtracking (k, n, sum, i+1);
            //回溯
            sum -= i;
            path.removeLast();
        }

    }
}

原因：

在进行回溯时，直接将 sum 减去了 i，然后才移除了 path 的最后一个元素。这会导致在回溯时 sum 的值不是当前路径正确的和，因为 sum 在每次迭代时都被修改了，而在回溯时却只是简单地减去了当前的 i 值。

应该先将元素从 path 中移除，然后再减去对应的值，即先 path.removeLast() 再 sum -= i。这样才能正确地进行回溯操作，确保下一次迭代时 path 和 sum 的状态是正确的。

而且，单层递归时，没把i加到path里面。。。。

正确代码：

class Solution {
    //全局变量
    //path result
    List<List<Integer>> result = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
//在 backTracking 函数中，sum 的初始值为 0，这是因为我们在寻找组合数时需要从零开始累加元素，直到达到目标和。
        backtracking (k, n, 0,1);
        return result;

    }
    void backtracking (int k, int n, int sum, int startindex){
        //从n剪枝
        if (sum > n) return;
        //确定终止条件
        if (path.size()==k) {
            if (sum == n) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        //单层递归逻辑(要从k剪枝)
        for (int i=startindex; i<=9-(k-path.size())+1; i++) {
            path.add(i);
            sum += i;
            backtracking (k, n, sum, i+1);
            //回溯
            path.removeLast();
            sum -= i;            
        }

    }
}