用AI赚第一桶💰低成本搭建一套AI赚钱工具,源码可二开。 广告
**一. 题目描述** 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 <iostream> #include <vector> using namespace std; class Solution { public: vector<vector<int> > combinationSum3(int k, int n) { vector<vector<int> > result; vector<int> temp; combinationSum3DFS(k, n, 1, temp, result); return result; } private: void combinationSum3DFS(int k, int n, int level, vector<int> &temp, vector<vector<int> > &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题目,还需要深入研究。