其他
大家好,我是程序员学长~今天给大家带来一篇面试高频算法题之回溯算法的详细解析,全文包含6道大厂笔试面试算法真题,一举拿下回溯算法这个知识点,让算法不在成为进入大厂的绊脚石。如果喜欢,记得点个关注哟~本文有点长,在公众号浏览可能不方便,我已将本文制作成带目录的PDF版本,获取本文PDF版本,请扫下方二维码加我微信,备注算法。回溯算法全文概览回溯算法基础知识回溯算法的基本思想回溯算法本质上就是一个枚举的过程。在枚举搜索的过程中尝试寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径;或者当寻找到问题的解后,将其加入结果中,然后“回溯”返回,尝试还有没有其他满足条件的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。回溯算法和贪心算法的区别贪心算法只能根据当前的状态,选择最优的走法,走向下一步,就和人的一生一样,只能在岔路口选择一条当前条件下最优的路走,过去就过去了,不能回退,只能一条路走到黑。而回溯算法,可以有重来的机会,比如选择了一条路,发现这条路不适合自己,然后回退到岔路口,重新来选择。这就是回溯的思想(类似于可以穿越一样)。回溯算法模板求解回溯算法的相关问题,实际上就是一个多叉树的遍历过程。在给出回溯算法模板之前,我们先来看几个概念。路径:表示已经做出的选择。选择列表:表示当前可以做的选择。结束条件:也就是到达多叉树的叶子节点,即⽆法再做选择。代码框架如下所示:result=[]def