Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
代码语言：javascript复制[[1,2,4]]Example 2:
Input: k = 3, n = 9
Output:
代码语言：javascript复制[[1,2,6], [1,3,5], [2,3,4]]给定一个数字，求用1-9的数字求和得到这个数的不同组合。
dfs，一路从leetcode刷过来这也不是什么难事。
代码语言：javascript复制class Solution {
public:
void dfs(int k, int now, int n, int sum, vector<vector<int>> &res, vector<int> path)
{
if(sum > n) return ;
if(k == 0)
{
if(sum == n) res.push_back(path);
return ;
}
if(now == 0) return ;
for(int i = now; i > 0; i--)
{
vector<int> tmp = path;
tmp.push_back(i);
dfs(k-1, i - 1, n, sum i, res, tmp);
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> path;
dfs(k, 9, n, 0, res, path);
return res;
}
};
