找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。提示:
2 <= k <= 91 <= n <= 60
解题思路：回溯 + 剪枝
这道题和 77. 组合 比起来还是差不多的，甚至简单一点，因为这道题的集合区间也就是取值范围已经给我们了：[1, ..., 9]，只不过我们是需要多一个变量来判断一下这个组合的值是否为我们要的值 n，是的话就尾插到 vv 中，不是的话直接 return 即可！
接下来就是回溯三部曲：
- 确定递归函数的返回值以及参数
- 因为我们最后要返回一个 vector<vector<int>> ，那么期间我们也得有一个 vector<int> 来记录当前符合条件的结果
- 除此之外，为了防止出现重复的组合，我们需要一个 startindex变量，比如这次是 [1, 2, 3] 中取 1，那么下一层递归中就要从 2 开始取，不然就会出现 11 的情况！所以需要 startindex来记录下一层递归，搜索的起始位置。
- sum（int）为已经收集的元素的总和，也就是 v 里元素的总和。
- 回溯函数终止条件
- 通过这道题我们很清楚的知道终止条件就是要判断这个最后结果的位数也就是 k，那么我们只需要判断 v 数组中的长度是否等于 k，等于说明要 return 了，如果此时我们的 sum 已经为目标值 n，则将当前的结果集放到 vv 中，并且 return；否则的话直接 return 即可！
- 单层搜索的过程
- 本题和 77. 组合 区别之一就是集合固定的就是 9 个数 [1,...,9]，所以 for 循环固定 i<=9 即可！
剩下的就是剪枝工作啦，可以参考 77. 组合 这道题的笔记，这里直接给出结果，想必大家看上面的树形图的时候已经想到了。
如图：
for 循环的范围也可以剪枝，i <= 9 - (k - v.size()) + 1 就可以了！
class Solution {
public:
void backtracking(int k, int n, int startindex, int sum)
{
// 递归终止条件
if(v.size() == k)
{
// 只有当sum满足n才尾插到vv
if(sum == n)
vv.push_back(v);
return;
}
for(int i = startindex; i <= 9 - (k - v.size()); ++i) // 剪枝优化
{
v.push_back(i); // 处理
backtracking(k, n, i + 1, sum + i); // 递归，注意sum+i在这里放到函数中相当于已经处理和回溯了，因为传递过去的实参对这里的sum其实并没有改变
v.pop_back(); // 回溯
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1, 0);
return vv;
}
private:
vector<int> v;
vector<vector<int>> vv;
};