LC.P216[组合总和III]

方法一：回溯+剪枝

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
class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int k;

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        dfs(1, n);
        return ans;
    }

    private void dfs(int i, int s) {
        if (s == 0) {
            if (path.size() == k) {
                ans.add(new ArrayList<>(path));
            }
            return;
        }
        if (i > 9 || i > s || path.size() >= k) {
            return;
        }
        // 不选
        dfs(i + 1, s);

        // 选
        path.add(i);
        dfs(i + 1, s - i);
        path.remove(path.size() - 1);
    }
}
  • 时间复杂度：$O(C_9^k \times k)$
  • 空间复杂度：$O(k)$