7.2组合总和(LC216-M)

2023-12-20 12:53:39

算法:

以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;            
        }

    }
}

文章来源:https://blog.csdn.net/m0_50696252/article/details/135101655
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。