组合总和 III

搜索组合的模板

dfs 函数定义：void dfs(int start, int n, int k);

  1. 记录一个 start，意义为当前这个数最小可以从几开始搜。
  2. 记录一个 k，意义为当前搜索了几个数。
  3. 记录一个 n，意义为当前的总和是多少。
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:
  vector<vector<int>> ans;
  vector<int> path;
  vector<vector<int>> combinationSum3(int k, int n) {
    dfs(1, n, k);
    return ans;
  }
  void dfs(int start, int n, int k) {
    if (!n) {
      if (!k) {
        ans.push_back(path);
      }
    } else if (k) {
      for (int i = start; i <= 9; i++) {
        if (n >= i) {
          path.push_back(i);
          dfs(i + 1, n - i, k - 1);
          path.pop_back();
        }
      }
    }
  }
};