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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!