這道題在回溯的基礎上加入了剪枝操作。回溯方面我就不過多贅述，與組合(力扣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;}
};