【算法练习Day21】组合&&剪枝

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待

本期我们将进入回溯算法的练习。回溯算法通常和递归三部曲差不多，都是以确定递归函数返回值和参数，通常返回值是void，参数可以在我们写逻辑部分时候再慢慢确定，收获结果（结束跳出判断），和单层逻辑部分，三部分组成。

回溯算法可以用来解决很多正常情况无法用其他算法求解的问题，例如排列组合问题，子串问题，切割问题，棋盘问题。难度我是从低到高列出来的，其中以排列组合问题较易入手，棋盘问题为最难。

下面我们先来看一个经典例题

组合

77. 组合 - 力扣（LeetCode）

组合问题，在1-n这个范围内，找到所有k个数的组合放到数组内然后返回。

首先我们要创立两个数组，一个是二维数组存储的是每一个答案的组合result，另一个是承接每一个k个数的组合数组path，用它把数据放入二维数组内。然后我们需要一个递归函数，收获结果的条件是path里面的数据个数等于k个，这时候说明我们已经有了一个答案，可以将它们放入result里了。那么如何判断这里面的数据是否是我们所需要的呢？在收获结果部分我们并不做判断，判断的逻辑而是体现在单层递归逻辑，不符合的肯定不会被写入，值得注意的是，{1，2}和{2，1}组合是一样的答案，不能做重复的录入，因为组合是不讲究数据顺序的，只看数据的内容。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n,int k,int startIndex)
    {
        if(path.size()==k)
        {
            result.push_back(path);
            return;
        }
        for(int i=startIndex;i<=n;i++)
        {
            path.push_back(i);
            backtracking(n,k,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n,k,1);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

递归是纵向的取数据，而下面的单层逻辑也就是for循环是横向的在给定区间内取搜索数据。很重要的一点是我们在创立这个函数时候一定要有个start来记录我们每一次进入循环的起始位置。它很重要，它标记着我们下一个数要取什么数，其次起作用的就是i++，在我们满足了k个数要将数据放入result后，我们会进行下一步的回溯过程，也就是pop将最后一位取出来，然后i++放入新的数据，这也是回溯的效果，没有pop的回溯，数组满了我们就无法继续取值了，最后是递归传入的start的值，不是start+1，而是i+1，因为我们录入数据的时候用的就是push_back（i），所以我们要传入的就是i+1，这是一种解释，第二种解释是模拟，当我们k=2，n=4时，起初的1，2、1，3、1，4是正确传入的，但是当到了向上回溯两次时，i=1，start=1时，我们i++传入的push是2，如果我们继续传入start+1，会导致得到2，2这个结果，只有我们传入i++，才能使下一次递归i变成3。

剪枝

虽然回溯算法是纯暴力搜索答案的，但是我们也可以通过一个小技巧：剪枝 来剪掉一些没有必要的继续的递归的的一些条件 ，来使回溯算法的效率得到一些提高。这道题的剪枝思路可以是在for循环的判断进入循环部分，进行对判断部分的修改，以达到剪枝的效果。

实际上很多剪枝部分都是要在这里进行改变的。那么我们剪枝的思路是怎样的呢？当这里的k是需要将两个数放入答案数组的，但是我们遍历到最后一个数时候，它只能装下一个数，这还有必要再递归了吗，没有必要了，但是我们仅仅是为了省去一点点递归步骤吗？并不是，当k值较大时候，这种效果很明显，当k值较大时候，我们剩下很多数都是取不到的，因为可以装进数组中的值不够，而且这些树枝实际上是有深度的，可以画一棵树来模拟一下。比如说k=5，n=10时候，那么k=6之后的树枝我们都剪了下去，这样效率的提升是很明显的。

那么如何将该思路体现在代码上呢？我们很容易的就可以知道path.size（）代表的是当前的数组有几个数据，k-path.size（）是表示我们还需要传进去几个数值就满了，那么我们用n-（k-path.size（））+1表示我们最多可以从哪个数开始递归，超过这个范围，就表示当前的数字不可能找得到正确答案了，为啥要+1呢，是因为我们是从1-n的范围，+1是为了和前面对齐，带一个数字进去就明白为什么了。那么又有疑问了，如果每一次进来都是这个范围，那么我们怎么能继续递归下去呢？

例如当k=3，n=4时候，我们知道这个范围应该是i<=1,那接下来还是这样的范围怎么能让i=2传进去呢？不要忘了，这个判断条件的值是实时发生变化的，由于path.size（）的关系，它里面有几个数字我们得到的范围都是不一样的，所以大可不用担心，下面把剪枝代码也一并给出。

class Solution {
public:
	vector<vector<int>>result;
	vector<int>path;
	void backtraking(int n,int k,int start){
	    if(path.size()==k){
	        result.push_back(path);return ;
	    }
	    for(int i=start;i<=n-(k-path.size())+1;i++){
	        path.push_back(i);
	        backtraking(n,k,i+1);
	        path.pop_back();
	    }
	}
    vector<vector<int>> combine(int n, int k) {
        backtraking(n,k,1);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结：

今天我们开启了回溯算法专题，完成了组合、剪枝的学习，相关的思想需要多复习回顾。接下来，我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~