组合和三链接链接：https://leetcode-cn.com/problems/combination-sum-iii/求所有k个数加起来等于n的组合。组合中只允许有1到9的正整数，每个组合中不能有重复的数字。解释：所有数字都是正整数。解决方案集不能包含重复的组合。示例1：输入：k=3,n=7输出：[[1,2,4]]示例2：输入：k=3,n=9输出：[[1,2,6],[1,3,5],[2,3,4]]思路本题是在集合[1,2,3,4,5,6,7,8,9]中求和为n的k个数的组合。和77组合相比，无非就是多了一个限制。本题是求和为n的k个数的组合，且整个集合已经固定[1,...,9]。想到这里，做了77.组合之后，这道题就简单多了。这道题中k相当于树的深度，9（因为整个集合是9个数）就是树的宽度。比如k=2,n=4，就是在集合[1,2,3,4,5,6,7,8,9]。选择过程如图：CombinationSumIII。可以看出只有最后的集合(1,3)和4之和满足条件。回溯三部曲确定递归函数的参数同77.组合，还是需要一个一维数组path存放合格结果，一个二维数组result存放结果集。这里我还是把path和result定义为全局变量。至于为什么命名为路径？从上面的树结构可以看出，结果其实是一条从根节点到叶子节点的路径。vector>result;//存储结果集vectorpath;//满足条件的结果需要以下参数：targetSum(int)目标总和，即标题中的n。k(int)是标题中要求的k个数字的集合。sum(int)是收集到的元素的总和，即路径中元素的总和。startIndex(int)是下一层for循环搜索的起始位置。所以代码如下：vector>result;vectorpath;voidbacktracking(inttargetSum,intk,intsum,intstartIndex)其实这里也可以省略sum参数，每次targetSum减去选择的元素值，然后判断如果targetSum为0，则说明已经采集到符合条件的结果。为了直观理解，我还是加了一个sum参数。还需要强调的是，回溯法中递归函数的参数很难一次确定。一般先写逻辑，需要什么参数，填什么参数。判断终止条件什么时候终止？上面说了，k实际上限制了树的深度，因为只取k个元素是没有意义的，树越往深。因此，如果path.size()等于k，则终止。如果此时path中收集到的元素与(sum)和targetSum（即题目中描述的n）相同，则使用result收集当前结果。所以，终止代码如下：!=targetSum直接返回}这道题和77的区别之一，结合单层搜索过程是集合固定为9个数[1,...,9]，所以for循环固定i<=9如图：处理过程是收集每个第二次选择的元素相当于树结构中的边，sum用于统计路径中元素的总和。代码如下：for(inti=startIndex;i<=9;i++){sum+=i;path.push_back(i);backtracking(targetSum,k,sum,i+1);//注意i+1调整startIndexsum-=i;//回溯path.pop_back();//回溯}别忘了处理过程和回溯过程是一一对应的。处理量增加，回溯量就会减少！参考回溯算法，这个你应该知道！在模板中，不难编写如下C++代码：classSolution{private:vector>result;//存储结果集vectorpath;//限定结果//targetSum:目标总和，也是标题中的n。//k:标题中需要k个数字的集合。//sum：已经收集到的元素的总和，即路径中元素的总和。//startIndex：下一层for循环查找的起始位置。voidbacktracking(inttargetSum,intk,intsum,intstartIndex){if(path.size()==k){if(sum==targetSum)result.push_back(path);return;//如果path.size()==k但是sum!=targetSum直接返回}for(inti=startIndex;i<=9;i++){sum+=i;//处理path.push_back(i);//处理回溯(targetSum,k,sum,i+1);//注意i+1调整startIndexsum-=i;//回溯path.pop_back();//回溯}}public:vector>combinationSum3(intk,intn){result.clear();//你不能添加path.clear();//你不能添加backtracking(n,k,0,1);returnresult;}};剪枝这个题目，剪枝操作其实很容易想到，想必大家在看上面的树图的时候就已经想到了。如图：如果选中的元素之和已经大于n（图中的值为4），那么以后遍历就没有意义了，砍掉就好了。那么剪枝的地方一定要在递归终止的地方剪掉。剪枝代码如下：if(sum>targetSum){//剪枝操作return;}同77.组合，for循环的范围也可以剪枝，i<=9-(k-path.size())+1很好。最终的C++代码如下：classSolution{private:vector>result;//存储结果集vectorpath;//符合条件的结果voidbacktracking(inttargetSum,intk,intsum,intstartIndex){if(sum>targetSum){//剪枝操作return;//如果path.size()==k但是sum!=targetSum直接返回}if(path.size()==k){if(sum==targetSum)result.push_back(path);return;}for(inti=startIndex;i<=9-(k-path.size())+1;i++){//剪枝sum+=i;//处理path.push_back(i);//处理回溯(targetSum,k,sum,i+1);//注意i+1调整startIndexsum-=i;//回溯path.pop_back();//回溯}}public:vector>combinationSum3(intk,intn){result.clear();//不能加path.clear();//不能加backtracking(n,k,0,1);returnresult;}};summary开这道题和77.组合的区别有介绍。相对来说，增加了元素和的限制。做完77.组合再做这道题比较合适。分析差异后，还是将问题抽象成树状结构，按照回溯三部曲进行解释，最后给出剪枝的优化。相信做完这道题，大家应该对组合题有了一个初步的认识。
