成都网站设计新闻皮具网站设计

题目链接：
LeetCode-216-组合总和Ⅱ

解题思路：回溯算法
注意事项注释中有

代码实现：

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);}}
}