组合总和III(力扣216)

这道题在回溯的基础上加入了剪枝操作。回溯方面我就不过多赘述，与组合(力扣77)-CSDN博客 大差不差，主要讲解一下剪枝(下面的代码也有回溯操作的详细注释)。我们可以发现，如果我们递归到后面，可能集合过小，无法满足题目要求的k个数的组合，为了保证我们一定可以找到k个数的组合，在for循环中遍历当前集合时，要控制选取元素的边界在哪。就是说我们不能选到集合中太靠后的元素，这会导致递归的子集过小，无法选出k个数的组合。另外，当我们选出来的数字已经大于目标和时，可以直接退出递归，这也是一种剪枝。大家可以结合我下面的代码及注释理解此题。

代码及注释如下：

class Solution {
public://创建全局变量存储结果vector<int> path;//存储一个组合vector<vector<int>> result;//存储所有满足条件的组合void backtracking(int k,int n,int startIndex,int sum){//剪枝1：如果和已经大于目标和，可以直接退出递归if(sum > n){return;}//终止条件：找到k个数的组合，则退出递归if(path.size() == k){if(sum == n){result.push_back(path);return;}return;}//遍历当前集合的各个数字//剪枝2：如果集合中的数过少，就无法满足组合为k个数，根据这个条件找到每一层递归i的临界处for(int i = startIndex;i <= 9 - (k - path.size()) + 1;i++){sum += i;path.push_back(i);//递归更小的集合backtracking(k,n,i + 1,sum);//回溯操作path.pop_back();sum -= i;}} vector<vector<int>> combinationSum3(int k, int n) {backtracking(k,n,1,0);return result;}
};