组合Leetcode问题链接：https://leetcode-cn.com/problems/combinations/给定两个整数n和k，返回k个数从1...n的所有可能组合。示例：输入：n=4,k=2输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]这道题是回溯法的经典题。直接的解决方案当然是使用for循环。例如，示例中的k为2。很容易想到使用两个for循环，这样输出就可以输出和例子中一样的结果。代码如下：intn=4;for(inti=1;i<=n;i++){for(intj=i+1;j<=n;j++){cout<>result;//存放合格结果的集合vectorpath;//用于存放合格结果。其实不定义这两个全局遍历也是可以的。把这两个变量放入递归函数的参数中，但是函数中参数太多影响可读性，所以我定义了全局变量。函数中必须有两个参数。既然是k在集合n中的个数，那么n和k就是两个int参数。然后需要一个参数，就是int变量startIndex。该参数用于记录集合在本层递归中从哪里开始遍历（集合为[1,...,n]）。为什么我们有这个startIndex？每次从集合中选择一个元素时，可选范围都会随着选择的进行而缩小。调整可选范围取决于startIndex。从下图红线可以看出，集合[1,2,3,4]取1后，下一层递归会取[2,3,4]中的数，然后下一层递归的如何知道从[2,3,4]中取数取决于startIndex。组合2需要startIndex记录下一级递归，查找的起始位置。那么整体代码如下：vector>result;//存储符合条件的结果集合vectorpath;//用于存储单个符合条件的结果voidbacktracking(intn,intk,intstartIndex)是什么回溯函数的终止条件是到达所谓的叶节点了吗？如果路径数组的大小达到k，就意味着我们找到了一个子集大小为k的组合。图中path存放的是根节点到叶子节点的路径。如红色部分所示：组合3使用此时的结果二维数组保存路径，终止本层的递归。所以终止条件代码如下：if(path.size()==k){result.push_back(path);return;}单级搜索过程回溯法的搜索过程是一个树结构的遍历过程，如下图所示，可以看出for循环用于水平遍历，递归过程为垂直遍历。组合1这样，我们就遍历了图中的树。for循环每次都从startIndex开始遍历，然后把取到的节点i用path保存起来。代码如下：for(inti=startIndex;i<=n;i++){//水平遍历控制树path.push_back(i);//处理节点回溯(n,k,i+1);//递归：控制树的垂直遍历。注意，下一层搜索是从i+1开始的。总会有叶子节点，遇到叶子节点就返回。回溯的下半部分是回溯的操作，取消了本次处理的结果。关键点都说完了，完整的组合题C++代码如下：存储符合条件的结果路径.push_back(i);//处理节点回溯(n,k,i+1);//递归path.pop_back();//回溯，撤销处理的节点}}public:vector>combine(intn,intk){result.clear();//可以不写path.clear();//可以不写backtracking(n,k,1);returnresult;}};记住我们说的是回溯算法，你应该知道这些！是否给出了回溯方法模板？如下：voidbacktracking(参数){if(终止条件){存储结果；return;}for(selection:elementsinthecollectionofthislayer(树中子节点的个数为集合的大小)){处理节点;backtracking(path,selectionlist);//递归回溯，撤销处理结果}}对比一下这道题的代码，是不是觉得有点像！所以有了这个模板，解决问题就有了一个大概的方向，完全没有头绪。综上所述，组合问题是回溯法求解的经典问题。一开始给大家举个很形象的例子，就是n为100，k为50，直接思路需要50层for循环。于是引入回溯法来解决k级for循环嵌套的问题。然后进一步将回溯法的搜索过程抽象成树状结构，搜索过程可以直观的看出来。然后用回溯法三部曲一步步分析函数参数、终止条件和单层搜索的过程。Pruningoptimization我们说过回溯法虽然是暴力搜索，但是有时候也可以进行剪枝优化。在遍历的过程中，有如下代码：for(inti=startIndex;i<=n;i++){path.push_back(i);backtracking(n,k,i+1);path.pop_back();}这个遍历的范围是可以剪枝优化的，怎么优化呢？举个例子，如果n=4，k=4，那么在for循环的第一层，从元素2开始遍历是没有意义的。在第二层for循环中，从元素3开始遍历是没有意义的。这个有点抽象，如图：Combination4中的每个节点（图中的矩形）代表了这一层的一个for循环，所以如果每一层的for循环从第二个数开始遍历，所有的都没有有道理，都是无效遍历。因此，可以剪枝的地方就是递归中每一层的for循环选择的起始位置。如果for循环选择的起始位置之后的元素个数不够我们需要的元素个数，那么就不需要查找了。注意代码中的i是for循环中选择的起始位置。for(inti=startIndex;i<=n;i++){接下来看优化过程如下：被选中的元素个数：path.size();还需要的元素个数为：k-path.size();在集合n中，最多起始位置为：n-(k-path.size())+1，为什么有一个+1到开始遍历，因为包括起始位置，如果我们是左闭集。比如n=4,k=3，当前选中的元素为0（path.size为0），n-(k-0)+1就是4-(3-0)+1=2。这是合理的从2开始搜索，可以是[2,3,4]的组合。如果你在这里不明白，我建议你举个例子知道你是否需要+1。所以优化后的for循环为：for(inti=startIndex;i<=n-(k-path.size())+1;i++)//优化后i为本次搜索的起始位置，整体代码为如下：return;}for(inti=startIndex;i<=n-(k-path.size())+1;i++){//优化的地方path.push_back(i);//处理节点回溯(n,k,i+1);path.pop_back();//回溯，撤销处理节点}}public:vector>combine(intn,intk){backtracking(n,k,1);returnresult;}};cutBranchsummary在这篇文章中，我们对组合问题的回溯法代码进行了剪枝和优化。这个优化如果不画出来，其实很难理解和解释清楚。所以我还是把整个回溯过程抽象成一个树结构，然后可以直观的看出剪枝在哪里。其他语言版本JavaclassSolution{List>result=newArrayList<>();LinkedListpath=newLinkedList<>();publicList>combine(intn,intk){combineHelper(n,k,1);returnresult;}/***每次从集合中选择一个元素时，可选范围会随着选择的进行而缩小。调整可选范围就是依靠startIndex*@paramstartIndex来记录这一层在递归中，从哪里开始遍历集合（集合是[1,...,n]）。*/privatevoidcombineHelper(intn,intk,intstartIndex){//终止条件if(path.size()==k){result.add(newArrayList<>(path));return;}for(inti=startIndex;i<=n-(k-path.size())+1;i++){path.add(i);combineHelper(n,k,i+1);path.removeLast();}}}PythonclassSolution:defcombine(self,n:int,k:int)->List[List[int]]:res=[]#存储符合条件的结果集path=[]#用于存储符合条件的结果defbacktrack(n,k,startIndex):iflen(path)==k:res.append(path[:])returnforiinrange(startIndex,n+1):path.append(i)#processing节点回溯(n,k,i+1)#recursivepath.pop()#回溯，撤销处理节点回溯(n,k,1)returnresGovarres[][]intfunccombine(nint,kint)[][]int{res=[][]int{}ifn<=0||k<=0||k>n{returnres}backtrack(n,k,1,[]int{})returnres}funcbacktrack(n,k,startint,track[]int){iflen(track)==k{temp:=make([]int,k)copy(temp,track)res=append(res,temp)}iflen(track)+n-start+1
