友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
-
只使用数字
1到9 -
每个数字 最多使用一次
返回 所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
-
2 <= k <= 9 -
1 <= n <= 60
思路分析
回溯
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-30 07:16:18
*/
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>(k);
backtrack(k, n, result, path, 1);
return result;
}
private void backtrack(int count, int sum,
List<List<Integer>> result,
List<Integer> path, int start) {
if (path.size() > count) {
return;
}
if (sum == 0 && path.size() == count) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= 9; i++) {
if (i > sum) {
break;
}
path.add(i);
backtrack(count, sum - i, result, path, i + 1);
path.removeLast();
}
}
参考资料
-
216. 组合总和 III - 官方题解 — 二进制枚举的思路有意思。在 77. Combinations 的官方题解中，有一个子集枚举的解题框架。