力扣日记:【回溯算法篇】216. 组合总和 III
日期:2023.1.22
参考:代码随想录、力扣
216. 组合总和 III
题目描述
难度:中等
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:
- 只使用数字1到9
- 每个数字 最多使用一次
- 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。
提示:文章来源:https://www.toymoban.com/news/detail-819168.html
- 2 <= k <= 9
- 1 <= n <= 60
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
int sum = 0; // 记录当前和
// 树的宽度为集合长度(1~9),树的深度为k(最多递归k层)
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1); // 从1开始
return result;
}
// 返回值为void,参数为k, n以及当前集合开始遍历的位置
void backtracking(int k, int n, int startindex) {
// 终止(判断)
// 最多只能有k个数
if (path.size() == k) {
if (sum == n) {
// 如果满足条件则添加进结果集
result.push_back(path);
}
return;
}
// 未到达k, 则 for 循环遍历当前集合
// 剪枝1:如果剩余可遍历的元素个数不足以构成组合则不需要再遍历(注意这里最大就是9,即组合问题的n=9)
// path.size() + (9 - startindex + 1) >= k
// 剪枝2:能在这里遍历说明组合path还未到达k个,但如果此时sum已经>=n,则越往后的sum肯定超过n,则不需要再遍历
if (sum >= n) return;
for (int i = startindex; i <= path.size() + 9 + 1 - k; i++) {
// 处理节点
path.push_back(i);
sum += i;
// 递归
backtracking(k, n, i + 1);
// 回溯
path.pop_back();
sum -= i;
}
return;
}
};
复杂度
时间复杂度:
空间复杂度:文章来源地址https://www.toymoban.com/news/detail-819168.html
思路总结
- 思路与77.组合基本一致,只是多了一个“相加之和为n”的判断
- 注意这道题,集合即为[1,2,…,9],即类比77.组合问题的n在本题中固定为9(注意与本题的n区别),即for循环遍历的最大个数为9。从这个集合中找k个值,使其和为n。
- 剪枝可从两处进行,一是遍历剩余集合个数;二是sum>n的情况(这里我与代码随想录的区别是,代码随想录是在函数最开始(终止条件之前)就对sum进行判断(如果sum>n则return),我是在终止条件之后,即如果组合个数未达到k个,但是sum却>=n了(等于n也不行),则不满足需剪枝
- sum也可以设置为backtracking的参数
到了这里,关于力扣日记1.22-【回溯算法篇】216. 组合总和 III的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!