题目：
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
题目链接：https://leetcode-cn.com/problems/combination-sum-iii
思考：
1、这道题可以用深度优先搜索dfs来解，dfs的方法主要在于3点：第一，终止条件；第二循环调用；第三，变化条件
2、对应到这个题中，计算和为n的k个数，k个数用完了就是终止了；循环条件是 不断调用下一个dfs，且其中用到的数组值是当前数组值+1；变化条件就是 和n在不断减少，k也在不断减少；具体变现形式见代码
C++代码
class Solution {
// 所有相加之和为 n 的 k 个数的组合
// dfs 回溯 + 剪枝
vector<vector<int>> ret;
vector<int> curr;
void dfs(int k, int n, int i){
if(n<0){
return;
}
if(k==0){
if (n==0){
ret.push_back(curr);
}
return ;
}
for(int j=i+1; j<=9; j++){
curr.push_back(j);
dfs(k-1,n-j,j);
curr.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, 0);
return ret;
}
};
Python代码：
class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
ret = []
def dfs(k, n, i, curr):
if n<0:
return
if k==0:
if n==0:
ret.append(curr)
return
for j in range(i+1, 10):
dfs(k-1, n-j, j, curr+[j])
dfs(k,n,0,[])
return ret
