题目链接：
LeetCode-216-组合总和Ⅱ
解题思路：回溯算法
注意事项注释中有文章来源：https://www.toymoban.com/news/detail-696770.html
代码实现：文章来源地址https://www.toymoban.com/news/detail-696770.html
class Solution {
/**
* 和为 n，个数为 k
* 求的是组合，不要求顺序
* 递归的深度是 k
*/
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(k, n, 1, 0);
return res;
}
// 两个全局变量，一个一维数组放取的元素，一个二维数组放结果
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public void backtracking(int k, int targetSum, int startIndex, int sum){
if (sum > targetSum||path.size()>k){// 这里需要再增加一个条件，sum>目标值返回，个数大于k也返回，可以根据个数提前结束判断，节省时间
return;
}
if (path.size() == k && sum == targetSum){
res.add(new LinkedList<>(path));// 添加到res中的方法一
// List<Integer> tmp = new ArrayList<>();// 添加到res中的方法二，也可以一个一个的添加
// for(int t:path){
// tmp.add(t);
// }
// res.add(tmp);
return;
}
for (int i = startIndex; i <=9 ; i++) {// 区间可以剪枝
path.add(i);
// sum += i; // 不推荐这种写法,每次会改变sum的值
backtracking(k,targetSum,i+1, sum+i); // 直接写到参数里，sum的值也不会变
// sum -= i;// 探了之后发现不行
path.remove(path.size()-1);
}
}
}
到了这里，关于LeetCode-216-组合总和Ⅱ的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
