216. 组合总和 III
找出所有相加之和为 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]]
解题思路
有了77. 组合的铺垫，这道题就容易很多，只是多了一个限制条件而已。
代码(C++)
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backTracking(int k, int n, int startIndex, int sum) {
//当找到 k 个数时，判断这 k 个数的和是否等于 n, 如果相等就存入 结果集 中并返回，如果不相等则直接返回。
if (path.size() == k) {
if (sum == n) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9; i++) {
path.push_back(i);
sum += i;
backTracking(k, n, i + 1, sum);
path.pop_back(); // 回溯
sum -= i; // 回溯
}
}
vector<vector<int>> combinationSum3(int k, int n) {
path.clear();
result.clear();
backTracking(k, n, 1, 0);
return result;
}
};
这道题有两个可以优化的地方：
-
与77. 组合一样，当剩余元素的个数少于 k 个时，没有必要在往下搜索。所以在 for 循环处剪枝：
i<=9-(k-path.size)+1 -
另外，如果当前选取的所有路径里面节点(节点个数小于或等于 k)之和已经大于 n 时，也没有必要继续往下搜索了。
代码(C++)
// 剪枝优化
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backTracking(int k, int n, int startIndex, int sum) {
if (path.size() == k) {
if (sum == n) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 第一个优化
path.push_back(i);
sum += i;
if (sum <= n) backTracking(k, n, i + 1, sum); // 第二个优化，只有当前的和小于等于 n 才进入下一次递归
path.pop_back(); // 回溯
sum -= i; // 回溯
}
}
vector<vector<int>> combinationSum3(int k, int n) {
path.clear();
result.clear();
backTracking(k, n, 1, 0);
return result;
}
};
代码(JS)
let path = [];
let result = [];
var combinationSum3 = function(k, n) {
path = [];
result = [];
backTracking(k, n, 1, 0);
return result;
};
const backTracking = (k, n, start, sum) => {
if (k === path.length) {
if (sum === n) result.push([...path]);
return;
}
for (let i = start; i <= 9 - (k - path.length) + 1; i++) {
path.push(i);
sum += i;
if (sum <= n) backTracking(k, n, i + 1, sum);
path.pop();
sum -= i;
}
}