Java实现 LeetCode 216. 组合总和 III(三)

时间:2022-06-07 09:06:20

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