7.4组合总和(LC39-M)

2023-12-23 17:49:46

算法:

组合问题,用回溯。

画树

回溯三部曲:

1.确定函数返回值和参数:

返回值:void

参数:

candidates, target(题目中给出的)

sum:统计每个组合的和,是否==target

statrtindex:在一个集合中求组合,需要statrtindex来确认下一次递归的位置

2.确定终止条件:

sum>target,终止;sum==target=,收集结果

从叶子节点可以清晰看到,终止只有两种情况,sum大于target和sum等于target。

3.单层递归逻辑

for (int i = startIndex; i < candidates.size(); i++) {
    sum += candidates[i];
    path.push_back(candidates[i]);
    backtracking(candidates, target, sum, i); // 关键点:不用i+1了,表示可以重复读取当前的数
    sum -= candidates[i];   // 回溯
    path.pop_back();        // 回溯
}

剪枝优化:

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

在for循环中加入条件:

sum + candidates[i] <= target

正确代码:

class Solution {
//全局变量path和result
    List<List<Integer>> result = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target)
//`int[] candidates` 表示一个整数数组,可以包含多个整数元素。你可以通过`candidates[0]`、`candidates[1]`等方式访问数组中的不同元素。
//int target` 则表示一个单独的整数变量,只能存储一个整数值。
     {if (candidates == null) return result;
     backtracking(candidates, target, 0, 0);
     return result;
    }
    void backtracking(int[] candidates, int target, int sum, int startindex){
    //确定终止条件
    if (sum > target) return;
    if (sum == target) {
        result.add(new LinkedList(path));
        return;
    }
    //单层递归逻辑
    for (int i = startindex; i < candidates.length && sum <= target; i++){
        path.add(candidates[i]);
        sum += candidates[i];
        backtracking(candidates, target, sum, i);
        //回溯
        sum -= candidates[i];
        path.removeLast();
    }
    }
}

时间空间复杂度:

  • 时间复杂度: O(n * 2^n),注意这只是复杂度的上界,因为剪枝的存在,真实的时间复杂度远小于此
  • 空间复杂度: O(target)

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