找出所有相加之和为 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]]
二、求解算法
① 回溯+剪枝
本题就是在 [1,2,3,4,5,6,7,8,9] 这个集合中找到和为 n 的 k 个数的组合，相对于 【数据结构与算法】之N个数中有K个数可能的组合算法 ，无非就是多了一个限制，要找到和为 n 的 k 个数的组合，而整个集合已经是固定 [1,…,9]，理解了N个数中有K个数可能的组合算法之后本题就比较简单了。
k 相当于了树的深度，9（因为整个集合就是9个数）就是树的宽度。例如 k = 2，n = 4 的话，就是在集合[1,2,3,4,5,6,7,8,9] 中求 k（个数） = 2，n（和） = 4 的组合。
选取过程如下图所示，可以看出，只有最后取到集合（1，3）和为 4 符合条件：
回溯三部曲：
确定递归函数参数：
和 【数据结构与算法】之N个数中有K个数可能的组合算法 一样，依然需要一维数组 path 来存放符合条件的结果，二维数组 result 来存放结果集，这里依然定义 path 和 result 为全局变量，至于为什么取名为 path？从上面树形结构中，可以看出，结果其实就是一条根节点到叶子节点的路径。
class Solution {
private:
vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (sum > targetSum) { // 剪枝操作
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
if (path.size() == k) {
if (sum == targetSum) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
sum += i; // 处理
path.push_back(i); // 处理
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back(); // 回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
result.clear(); // 可以不加
path.clear(); // 可以不加
backtracking(n, k, 0, 1);
return result;
}
};
Java 示例：
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return result;
}
private void backTracking(int targetSum, int k, int startIndex, int sum) {
// 减枝
if (sum > targetSum) {
return;
}
if (path.size() == k) {
if (sum == targetSum) result.add(new ArrayList<>(path));
return;
}
// 减枝 9 - (k - path.size()) + 1
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
sum += i;
backTracking(targetSum, k, i + 1, sum);
// 回溯
path.removeLast();
// 回溯
sum -= i;
}
}
}
② 二进制（子集）枚举
组合中只允许含有 1−9 的正整数，并且每种组合中不存在重复的数字，意味着这个组合中最多包含 9 个数字，我们可以把原问题转化成集合 S={1,2,3,4,5,6,7,8,9}，要找出 S 的当中满足如下条件的子集：
大小为 k；
集合中元素的和为 n。
因此可以用子集枚举的方法来解决本题，即原序列中有 9 个数，每个数都有两种状态，「被选择到子集中」和「不被选择到子集中」，所以状态的总数为 29。用一个 9 位二进制数 mask 来记录当前所有位置的状态，从第到高第 i 位为 0 表示 i 不被选择到子集中，为 1 表示 i 被选择到子集中。当按顺序枚举 [0, 29−1] 中的所有整数的时候，就可以不重不漏地把每个状态枚举到，对于一个状态 mask，可以用位运算的方法得到对应的子集序列，然后再判断是否满足上面的两个条件，如果满足，就记录答案。
如何通过位运算来得到 mask 各个位置的信息？对于第 i 个位置，可以判断 (1 << i) & mask 是否为 0，如果不为 0 则说明 i 在子集当中。当然，这里要注意的是，一个 9 位二进制数 i 的范围是 [0,8]，而可选择的数字是 [1,9]，所以需要做一个映射，最简单的办法就是当我们知道 i 位置不为 0 的时候将 i+1 加入子集。
当然，子集枚举也可以用递归实现。
C++ 示例：
class Solution {
public:
vector<int> temp;
vector<vector<int>> ans;
bool check(int mask, int k, int n) {
temp.clear();
for (int i = 0; i < 9; ++i) {
if ((1 << i) & mask) {
temp.push_back(i + 1);
}
}
return temp.size() == k && accumulate(temp.begin(), temp.end(), 0) == n;
}
vector<vector<int>> combinationSum3(int k, int n) {
for (int mask = 0; mask < (1 << 9); ++mask) {
if (check(mask, k, n)) {
ans.emplace_back(temp);
}
}
return ans;
}
};
Java 示例：
class Solution {
List<Integer> temp = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum3(int k, int n) {
for (int mask = 0; mask < (1 << 9); ++mask) {
if (check(mask, k, n)) {
ans.add(new ArrayList<Integer>(temp));
}
}
return ans;
}
public boolean check(int mask, int k, int n) {
temp.clear();
for (int i = 0; i < 9; ++i) {
if (((1 << i) & mask) != 0) {
temp.add(i + 1);
}
}
if (temp.size() != k) {
return false;
}
int sum = 0;
for (int num : temp) {
sum += num;
}
return sum == n;
}
}
复杂度分析：
时间复杂度：O(M×2M)，其中 M 为集合的大小，本题中 M 固定为 9，一共有 2M 个状态，每个状态需要 O(M+k)=O(M) 的判断 （k≤M），故时间复杂度为 O(M×2M)；