文章目录

一、什么是回溯算法？

回溯，也就是回退。举个例子，你从A地出发，要到B地去，但是从A地出发有多条路，在每条路上可能会遇到多条路口，回溯就是你先走其中一条路，比如路1，走完路1然后再回到A地，然后走路2，依次走剩下的路，直到走完所有的路。为了简单说明,只画了几个点辅助理解.

从A点出发时,前面有两条路,1号线和2号线,选择1号线出发,走完1号线所有的路再回来走2号线(当然,如果走1号线时满足了要求就不必回来了),选择1号线出发:

到达中间点M,而中间点M前面又有3条路线,也是先选择其中一条,之后再回来选择其他路线,这里选择3号线:

到达中间点X,中间点X前面只有一条路,不管前面是不是终点B都需要继续走下去了,好处是这里没有其他的路,只有一条,所以也不用选择了.

幸运的是到达了终点B,如果只要求到达终点B，那现在就完成任务了，但是这里要说的是回溯，肯定不会这么简单，如果问题是从A到B有几条路线，或者求出最短的一条路线（图中没有写出路线的长短），那就得都走一遍了．比如说计算从A到B有几条路线，那现在就需要从９号线往回走：

达到点X之后,9号线已经走过了,所以不能再走了,只能沿着3号线往回走.你可能会说3号线也走过了,怎么可以走3号线呢,这是因为9号线已经达到了死胡同,就是没有其他的路线了,而沿着3号线还可以继续走其他没有走过的路线,比如4号线\5号线.

沿着3号线往回走达到点M之后,面前有4条路线,1条是沿着1号线往回走,1条是走过的3号线,不能再走了,还有两条没有走过的4号线和5号线,选择其中一条走下去:

到达点Y,发现Y是个死活同,走不下去了,所以只能回去了.然后继续走5号线,按照刚才的走法,遇到不同的情况,选择不同的走法:

1或多条没有走过的路线,选择其中1条走下去;走到终点\死胡同,就往回走;如果面前的路都走过了,那就再往回走.

直到所有的路都走过一遍.

啰了吧嗦说了这么多,看着其实一点都不复杂,只要上过小学,这些应该都能看懂,主要是怎么实现(突然想起来我老师说的:“就是编程不行呗”)

二、如何实现回溯算法呢?

要想实现回溯算法,还需要说明几个事情(回溯三要素),1.你走过的路线–路径;2.你可以走的路线-选择列表;3.结束条件.

1.先说说路径,就是你已经走过了哪些地方,比如说让你计算从A到B最短路径,你现在在X点呢,那你得记住从A点到X点走了多远吧,但是只记住一个数值多远还不行,因为你之后还需要回退,还要减去3号线的距离,所以这里的路径应该是你走过路线的按顺序的集合,可以认为是一个数组,里面放着各个点;

2.其次就是选择列表,就是你需要知道接下来你可以往哪儿走啊,如果你从M点走过3号线,又回退到M点的时候,就不能再走3号线了,你怎么知道不能走了呢,你得记录一下哪个能走,哪个不能走啊(记录能走的即可).

3.最后就是结束条件了,当你走完所有的路线之后就是结束,如何知道结束呢,你得设置个条件啊,比如说在A点时,选择列表为空了,那就说明不能继续走下去了,就结束了.

这里举个例子:leetcode17题:电话号码的字母组合

class Solution {public:vector<string> letterCombinations(string digits) {}};

这个题比上面的例子还要简单些,它的前后没有关系,前边AB点的例子,从A走后,后面的情况是受A影响的,而这里不影响,它都是固定的.比如输入234257,第一个就是2,第二个就是3,不存在第二个值受第一个值的影响,不过很多题目都是受影响的.回溯三要素:

首先考虑路径,可以使用string的一个变量保存,遇到新的地点就添加,回退的时候就去掉string变量中最后的地点;然后是选择列表,完全可以将可选择的选项存到一个数组中,需要删除时,在数组中删掉,不过这样的消耗比较大,涉及数组的删除等,我们可以将开始的选择存储到列表,使用一个index索引指示哪些可以选择,比如index=2,则0-1就不能选择了,只有从2开始可以选择,并且是从小到大选择,否则的话就乱了套了.最后是结束条件,可以将选择完所有的string中的字符作为结束条件.

说一下解决回溯算法的套路吧,这是参考labuladong(微信公众号/网站/知乎)的框架(在这里十分感谢labuladong的硬核文章):

result = []def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径, 选择列表)撤销选择

开始我在做回溯算法题的时候一直有2个疑惑:选择1号线之后,再选择2号线时没有什么影响吗?怎么确定选择完1号线之后再选2号线呢?

关于第1个疑惑:其实是没有影响的,因为1号线在处理时,路径中会新增地点,而处理完之后,就会删除(这里就是回溯啦).所以当走完1号线,再走2号线的时候,路径还是只有起点A,因此不受影响;关于第二个问题,就是需要写个for循环,一次循环处理一次路线,整个for循环就是处理某个点之后的所有路线了.

说了这么多,最后的完整代码:

class Solution {public:vector<string> letterCombinations(string digits) {if( !digits.size() )return res;getLetter(digits,0);return res;}private:void getLetter(string& digits, int index) {if( index<0 )return;if( index>=digits.size() ) {res.push_back(str);return;}int k=digits[index]-'2';for( int i=0; i<letter[k].size(); ++i ) {str+=letter[k][i];getLetter(digits,index+1);str.erase(str.end()-1);}}public:vector<string> letter={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> res;string str="";};

三、总结

上述我的解法不是最好的,但这是我想到的可以解决问题的解法,里面还可以有一些优化,之后可能还会继续研究.

其实回溯算法理解起来并不难,主要是实现的时候可能会比较绕,其实是刚开始接触的时候,越想越理解不了,我觉得看一下上述的框架,然后做几道题找找感觉,应该就没问题了.

参考文章:回溯算法详解_labuladong

如果觉得《数据结构与算法--回溯的理解以及实现》对你有帮助，请点赞、收藏，并留下你的观点哦！