1 问题

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

2 解法

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。

class Solution {
public:vector<int> path;vector<vector<int>> res;void backtracking(int targetSum, int k, int startIndex){if(path.size() == k){if(targetSum == 0)res.push_back(path);return; //已存在k个数，但和不为target时也直接返回}//横向遍历1～9for(int i = startIndex; i <= 9; i++){//处理节点，将节点加入组合path.push_back(i);//目标和剩余的数targetSum -= i;//递归backtracking(targetSum, k, i + 1);//回溯targetSum += i;path.pop_back();} }vector<vector<int>> combinationSum3(int k, int n) {backtracking(n, k, 1);return res;}   
};

3 优化剪枝

已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。
那么剪枝的地方一定是在递归终止的地方剪，剪枝代码如下：

class Solution {
public:vector<int> path;vector<vector<int>> res;void backtracking(int targetSum, int k, int startIndex){//剪枝操作if(targetSum < 0)return;if(path.size() == k){if(targetSum == 0)res.push_back(path);return; //已存在k个数，但和不为target时也直接返回}//横向遍历1～9for(int i = startIndex; i <= 9; i++){//处理节点，将节点加入组合path.push_back(i);//目标和剩余的数targetSum -= i;//递归backtracking(targetSum, k, i + 1);//回溯targetSum += i;path.pop_back();} }vector<vector<int>> combinationSum3(int k, int n) {backtracking(n, k, 1);return res;}   
};