1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
helper(ans, new ArrayList<>(), 1, k, n);
return ans;
}
private void helper(List<List<Integer>> ans, List<Integer> curr, int pos, int k, int remain) {
if (curr.size() == k) {
if (remain == 0) {
ans.add(new ArrayList<>(curr));
}
return;
}
if (remain < 0) {
return;
}
for (int i = pos; i < 10; i++) {
curr.add(i);
helper(ans, curr, i + 1, k, remain - i);
curr.remove(curr.size() - 1);
}
}
}
|
就是轮流找人当开头. 递归函数的功能就是给它一个pos(也就是选数只能从哪里开始往后选), 以及要凑的数remain, 它能给我们找到所有凑的方式. 那么我们用一个curr数组, 把我们当前的选择记录的curr里面, 然后之后交给递归函数去找并在curr中append它找到的组合. 大概就是这样.
时间复杂度: O(c9k) 也就是从9个中挑k个, 看有几种挑法. 但是我们适当的剪枝, 也就是当没凑个k个时但是remain小于0时, 直接return, 没必要再找了. 因此时间会快一些. 15行的优化很重要.
空间复杂度: O(n) 我们最多选9个数字, 因此递归函数的深度也是9.
每次就是选一个数字当开头, 然后继续在可以的范围内再选数字当开头.
