可能需要回顧的文章;
leetcode 77. 組合 思考分析

1、題目

找出所有相加之和為 n 的 k 個數的組合。組合中只允許含有 1 - 9 的正整數，并且每種組合中不存在重復的數字。
說明：
所有數字都是正整數。
解集不能包含重復的組合。

2、遞歸

這一題和之前一題很像：
leetcode 77. 組合 思考分析
終止條件有兩個：sum==n && res.size() == k
回溯的過程中加入對sum值的修改。
修改一下遞歸函數的參數值，這樣，本題就做好了

class Solution {
public:vector<vector<int>> result;vector<int> res;int sum;void clear_solution_param(){result.clear();res.clear();sum=0;}void backtracking(int start,int end,int k,int n){//找到了k個數if(res.size() == k && sum == n){result.push_back(res);return;}for(int i=start;i<=end;i++){//處理結點；res.push_back(i);sum+=i;//遞歸,探索下一層backtracking(i+1,end,k,n);		//遞歸sum-=i;//回溯，撤銷處理結果res.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {clear_solution_param();backtracking(1,9,k,n);return result;}
};

3、剪枝優化

1、我們之前的終止條件其實限的有問題，如果res.size已經等于k了，那么就沒必要繼續搜索了，直接返回。sum是否等于n只是關系到我們是否得到正確答案。所以應該修改為：

if(res.size() == k)
{if(sum == n) result.push_back(res);return;			//如果size==k,但是sum!=n，直接返回
}

2、修改成上面那樣其實還是有冗余，我們注意到，如果sum>n，此時也沒有必要進行再次搜索了

if(sum>n) return;
if(res.size() == k)
{if(sum == n) result.push_back(res);return;			//如果size==k,但是sum!=n，直接返回
}

3、同leetcode 77. 組合 思考分析的剪枝操作：
我們已經選擇的元素個數為：res.size()
我們還需要的元素的個數為k-res.size()
所以最多從end-(k-res.size())+1的地方開始遍歷。

for(int i=start;i<=end-(k-res.size())+1;i++)
{//處理結點；res.push_back(i);sum+=i;//遞歸,探索下一層backtracking(i+1,end,k,n);		//遞歸sum-=i;//回溯，撤銷處理結果res.pop_back();
}

4、最終代碼：

class Solution {
public:vector<vector<int>> result;vector<int> res;int sum;void clear_solution_param(){result.clear();res.clear();sum=0;}void backtracking(int start,int end,int k,int n){if(sum>n) return;if(res.size() == k){if(sum == n) result.push_back(res);return;			//如果size==k,但是sum!=n，直接返回}for(int i=start;i<=end-(k-res.size())+1;i++){//處理結點；res.push_back(i);sum+=i;//遞歸,探索下一層backtracking(i+1,end,k,n);		//遞歸sum-=i;//回溯，撤銷處理結果res.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {clear_solution_param();backtracking(1,9,k,n);return result;}
};