216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
class Solution {
//结果集
public List<List<Integer>> lists = new ArrayList<>();
//临时集
public List<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
//回溯入口
backTracking(list, 0, 1, k, n, 0);
return lists;
}
public void backTracking(List<Integer> list, int index, int c, int k, int n, int sum){
//回溯出口
//保证是k个数字的累加，且，和为指定值
if(index == k && sum == n){
//满足添加入集合
List<Integer> currentList = new ArrayList<>();
currentList.addAll(list);
lists.add(currentList);
return;
}
//剪枝操作
if(sum > n){
return;
}
//回溯条件
for(int i = c; i <= 9; ++i){
list.add(i);
sum += i;
backTracking(list, index + 1, i + 1, k, n, sum);
list.remove(list.size() - 1);
sum -= i;
}
}
}
