天天算法 LeetCode-216-组合总和 III
216. 组合总和 III
题目链接
https://leetcode-cn.com/problems/combination-sum-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]]---------------------机智的思考线--------------------- ---------------------机智的思考线--------------------- ---------------------机智的思考线---------------------
解题方案
思路
- 标签：递归回溯
- 递归终止条件：数组中包含k个数，如果和为n则加入结果集，否则直接返回终止递归
- 递归过程：循环遍历1-9，将新数字加入临时数组中进入下一层递归，出来后再将其移除
- 回溯的关键在于，添加和移除，保证所有可能性都遍历到，整体结构和栈类似
回溯过程
代码
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
traceBack(k, n, 0, 1, new LinkedList<>());
return ans;
}
public void traceBack(int k, int n, int sum, int begin, LinkedList<Integer> list) {
if(k == 0) {
if(n == sum)
ans.add(new ArrayList<>(list));
return;
}
for(int i = begin; i < 10; i++) {
list.add(i);
traceBack(k - 1, n, sum + i ,i + 1, list);
list.removeLast();
}
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录