Combination Sum III
最后更新于：2022-04-01 22:57:38
**一. 题目描述**
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.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
~~~
[[1,2,4]]
~~~
Example 2:
Input: k = 3, n = 9
Output:
~~~
[[1,2,6], [1,3,5], [2,3,4]]
~~~
**二. 题目分析**
这道题题是组合之和系列的第三道题，跟之前两道Combination Sum 组合之和，前面两道题的联系比较紧密，变化不大，而这道跟它们最显著的不同就是这道题要求一个解中元素的个数为k。
实际上这道题是Combination Sum和Combination Sum II的综合体，两者杂糅到一起就是这道题的解法了。n是k个数字之和，如果n<0，则直接返回，如果n == 0，而且此时临时组合temp中的数字个数正好为k，说明此时是一个合适的组合解，将其存入结果result中。
**三. 示例代码**
~~~
#include
#include
using namespace std;
class Solution {
public:
vector > combinationSum3(int k, int n) {
vector > result;
vector temp;
combinationSum3DFS(k, n, 1, temp, result);
return result;
}
private:
void combinationSum3DFS(int k, int n, int level, vector &temp, vector > &result) {
if (n < 0) return;
if (n == 0 && temp.size() == k) result.push_back(temp);
for (int i = level; i <= 9; ++i) {
temp.push_back(i);
combinationSum3DFS(k, n - i, i + 1, temp, result);
temp.pop_back();
}
}
};
~~~
**四. 小结**
Combination Sum系列是经典的DFS题目，还需要深入研究。
';