当前位置：首页 > backend >正文

【代码随想录day 21】力扣 216.组合总和III

backend 2025/9/1 15:29:02

视频讲解：https://www.bilibili.com/video/BV1wg411873x/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
力扣题目：https://leetcode.cn/problems/combination-sum-iii/

在这里插入图片描述
这道题的主要思路如上所示，如同上一篇文章说的一样，任何回溯算法题都可以抽象为二叉树，需要注意的点如下：

回溯完之后，需要更新sum并且弹出i。
因为这里取的是组合，所以不用往前遍历，直接再i+1~9范围中取值即可。
当sum已经大于targetsum后，说明不可能再等于了，直接剪枝。
当剩余数字的数量不足以填满path了，比如k=3，即path里最多3个数，现在path已经存入一个数7，那只有789这一种组合，如果已经存入8，只有89一种组合，永远填不满，直接剪枝，即for循环中，i<9-(k-path.size())+1。

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(int targetSum, int k, int sum, int startIndex){//剪枝if(sum > targetSum){return;}//判断终止条件if(path.size() == k){//如果sum=targetsum就存进去if(targetSum == sum){result.push_back(path);}}//回溯for(int i = startIndex; i <= 9-(k-path.size())+1;i++){//计算sumsum = sum + i;//i压入pathpath.push_back(i);//回溯backtracking(targetSum, k, sum, i+1);//回溯完毕，sum还原sum = sum -i;//回溯完毕，弹出path去找下一个path.pop_back();}}
public:vector<vector<int>> combinationSum3(int k, int n) {result.clear();path.clear();backtracking(n, k, 0, 1);return result;}
};