4.组合总和lll（LeetCode216）
题目叙述：
找出所有相加之和为 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
思路：
1.回溯函数的参数以及返回值
-
没有返回值
-
我们需要startindex变量来标志着我们遍历的位置
-
并且需要一个一维数组path来存放当前的结果，一个二维数组result来存储最终的结果集。
-
targetSum（int）目标和，也就是题目中的n。
-
k（int）就是题目中要求k个数的集合。
-
sum（int）为已经收集的元素的总和，也就是path里元素的总和。
-
startIndex（int）为下一层for循环搜索的起始位置。
代码如下：
vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex)
2.回溯函数的结束条件
- 当我们数组中的元素个数等于k时，就收集到了k个元素，也就是我们满足题目的条件，此时就应该返回了
- 并且，如果此时的targetSum=sum了，就是满足我们题目要求的一个答案，我们就应该收集这个答案了。
代码如下：
if(path.size()==k){
if(sum==targetSum) result.push_back(path);
return;
}
3.单层递归的逻辑
- 此处我们是选择1-9的九个数字，因此单层递归的for循环应该是≤9
for(int i=startindex;i<=9;i++)
-
处理过程就是 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和
-
并且，我们还需要有回溯的过程，只要加了的话，我们要回到上一层，重新选择的话，此时我们就应该减回来
代码如下：
for(int i=startindex;i<=9;i++){
path.push_back(i);
sum+=i;
//此时这里是i+1，因为元素不能够重复取
backtracking(targetSum,k,sum,i+1);
//这里是回溯的逻辑，在之前加过的元素，如果我们要回溯到上一层再操作，就要减回来
sum-=i;
path.pop_back();
}
- 其实，我们也不需要对sum做加减的操作，直接对传入的参数进行操作，这样相当于是将回溯的逻辑隐藏在了递归函数中，不推荐这种做法。
for(int i=startindex;i<=9;i++){
path.push_back(i);
//此时这里是i+1，因为元素不能够重复取
backtracking(targetSum,k,sum+i,i+1);
path.pop_back();
}
代码：
- 我们根据上面三步的分析，不难得出代码：
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backtracking(int targetSum, int k, int startindex, int sum) {
if (path.size() == k) {
if (sum == targetSum)
result.push_back(path);
return;
}
for (int i = startindex; i <= 9; i++) {
sum += i;
path.push_back(i);
backtracking(targetSum, k, i + 1, sum);
//回溯的过程
path.pop_back();
sum -= i;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
//从1开始选
backtracking(n, k, 1, 0);
return result;
}
};
剪枝：
- 在这段代码中，我们可以有两个剪枝的过程。
- 第一就是如果我们发现当前的sum已经大于targetSum了，那么我们就没有必要就再往下进行遍历了，肯定没有符合条件的k个数相加为n。
void backtracking(int targetSum, int k, int startindex, int sum) {
//发现sum已经大于targetSum了，直接结束本层递归
if(sum>targetSum) return;
if (path.size() == k) {
if (sum == targetSum)
result.push_back(path);
return;
}
for (int i = startindex; i <= 9; i++) {
sum += i;
path.push_back(i);
backtracking(targetSum, k, i + 1, sum);
//回溯的过程
path.pop_back();
sum -= i;
}
}
- 第二就是单层递归的条件，我们没有必要从startindex遍历到9，只需要遍历到9-(k-path.size())+1即可
- 为什么只需要遍历到9-（k-path.size（））+1就可以了呢？这题的逻辑其实和我们之前讲解的LeetCode77组合总和有异曲同工之妙，我们数组中的元素个数为path.size（）个，我们还需要选择k-path.size（）个元素
- 又因为我们是从i开始,树的最底层,也就是递归的深度,是遍历到9结束,那么这个区间内的元素个数必须≥k-path.size()个
- 这个区间的元素个数为：9-i+1，那么9-i+1>=k-path.size（），可以推出i<=9-（k-path.size()）+1，就是说i至多从这个位置开始遍历
剪枝过程图如下：
-
本文借阅了代码随想录的原图，想要更加深入了解的可以去观看原作者所发的文章！