216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。

  • 解集不能包含重复的组合。

示例 1:
1
2
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
1
2
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

Solution：

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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(0,1,0,k,n);
        return ans;
    }
    //u:当前选择数的个数，a：当前可以枚举的位置，sum:当前组合数的和。
    void dfs(int u,int a,int sum,int k,int n){
        if(u == k && sum == n){
            ans.push_back(tmp);
            return;
        }
        if(a == 10){
            return;
        }
        if(sum > n) return;
        for(int i = a; i < 10; i++){
            tmp.push_back(i);
            dfs(u+1,i+1,sum+i,k,n);
            tmp.pop_back();
        }
        
    }
};