216. 组合总和 III
LeetCode题目要求
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
示例
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
解题思路
本题类似组合的解法, 刷刷刷 Day 24 | 77. 组合 ,根据回溯模板往下写即可,需要注意的就是有个加和的操作。与组合解法类似同样要进行剪枝优化
上代码
class Solution {
private List<List<Integer>> res = null;
private Deque<Integer> path = null;
public List<List<Integer>> combinationSum3(int k, int n) {
// k 是需要的数字的数量
// n 是 k 个数字的和
res = new ArrayList<>();
path = new LinkedList<>();
backtracking(k, n, 1, 0);
return res;
}
private void backtracking(int k, int n, int startIndex, int sum) {
// 剪枝操作,如果累加的 sum 已经大于目标值 n 了。就没必要继续下去
if (sum > n) {
return;
}
// 终止条件
if (path.size() == k) {
// 存储结果, 如果 sum 累加后与目标 n 相等,那么就存结果
if (n == sum) {
res.add(new ArrayList(path));
}
return;
}
// 遍历 i<n 可剪枝
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
// 累加操作,计算范围内数字和
sum += i;
// 递归操作,
backtracking(k, n, i + 1, sum);
// 回溯操作
sum -= i;
path.removeLast();
}
}
}
附:学习资料链接
标签:216,25,组合,int,res,sum,path,III From: https://www.cnblogs.com/blacksonny/p/17069912.html