找出所有相加之和为 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]]

Solution

回溯算法入门级详解 、代码随想录

其他组合问题： [39 组合总和]、[40 组合总和 II]

• 回溯法
• 组合问题，利用 begin 设置搜索起点

// @lc code=start
class Solution {
private:
    vector<vector<int>> res;

    void dfs(int k, int n, int start, vector<int>& cur){
        if(k==0 && n==0){
            res.push_back(cur);
            return;
        }

        for(int i=start; i<=9; ++i){
            if(k>0 && n>=i){  // 剪枝操作
                cur.push_back(i);
                dfs(k-1, n-i, i+1, cur);
                cur.pop_back();
            }
        }
        return;
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> cur;
        dfs(k, n, 1, cur);
        return res;
    }
};
// @lc code=end