代码随想录算法PDF.rar

「代码随想录」回溯算法精讲

该pdf是公众号「代码随想录」回溯算法专题的⽂章整理⽽来，共5万字，包含了30多张树形结构图、15

道⼒扣精选回溯题⽬，21篇回溯法精讲⽂章，由浅⼊深，⼀⽓呵成，这是全⽹最强回溯算法讲解！

本pdf题⽬⼤纲如下：

跟进最新⽂章，关注微信公众号「代码随想录」，你会发现相⻅恨晚！

很多⼩伙伴刷题的时候⾯对⼒扣上近两千道题⽬，感觉⽆从下⼿，我花费半年时间整理了Github项⽬：

「⼒扣刷题攻略」https://github.com/youngyangyang04/leetcode-master。 ⾥⾯有100多道经典算法

题⽬刷题顺序、配有40w字的详细图解，常⽤算法模板总结，以及难点视频讲解，按照list⼀道⼀道刷就

关于回溯算法，你该了解这些！

代码随想录出品：B站回溯算法视频讲解

什么是回溯法

回溯法也可以叫做回溯搜索法，它是⼀种搜索的⽅式。

在⼆叉树系列中，我们已经不⽌⼀次，提到了回溯，例如⼆叉树：以为使⽤了递归，其实还隐藏着回

溯。

回溯是递归的副产品，只要有递归就会有回溯。

所以以下讲解中，回溯函数也就是递归函数，指的都是⼀个函数。

回溯法的效率

回溯法的性能如何呢，这⾥要和⼤家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么

回溯法解决的问题

回溯法，⼀般可以解决如下⼏种问题：

组合问题：N个数⾥⾯按⼀定规则找出k个数的集合

切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式

⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集

排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式

棋盘问题：N皇后，解数独等等

相信⼤家看着这些之后会发现，每个问题，都不简单！

另外，会有⼀些同学可能分不清什么是组合，什么是排列？

组合是不强调元素顺序的，排列是强调元素顺序。

树的深度。

递归就要有终⽌条件，所以必然是⼀颗⾼度有限的树（N叉树）。

这块可能初学者还不太理解，后⾯的回溯算法解决的所有题⽬中，我都会强调这⼀点并画图举相应的例

⼦，现在有⼀个印象就⾏。

回溯法模板

这⾥给出Carl总结的回溯算法模板。

在讲⼆叉树的递归中我们说了递归三部曲，这⾥我再给⼤家列出回溯三部曲。

回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名⼤家随意。

回溯算法中函数返回值⼀般为void。

所以回溯也有要终⽌条件。

什么时候达到了终⽌条件，树中就可以看出，⼀般来说搜到叶⼦节点了，也就找到了满⾜条件的⼀条答

案，把这个答案存放起来，并结束本层递归。

所以回溯函数终⽌条件伪代码如下：

回溯搜索的遍历过程

在上⾯我们提到了，回溯法⼀般是在集合中递归搜索，集合的⼤⼩构成了树的宽度，递归的深度构成的

树的深度。

如图：

注意图中，我特意举例集合⼤⼩和孩⼦的数量是相等的！

回溯函数遍历过程伪代码如下：

for循环就是遍历集合区间，可以理解⼀个节点有多少个孩⼦，这个for循环就执⾏多少次。

backtracking这⾥⾃⼰调⽤⾃⼰，实现递归。

⼤家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这

本篇我们讲解了，什么是回溯算法，知道了回溯和递归是相辅相成的。

接着提到了回溯法的效率，回溯法其实就是暴⼒查找，并不是什么⾼效的算法。

然后列出了回溯法可以解决⼏类问题，可以看出每⼀类问题都不简单。

最后我们讲到回溯法解决的问题都可以抽象为树形结构（N叉树），并给出了回溯法的模板。

今天是回溯算法的第⼀天，按照惯例Carl都是先概述⼀波，然后在开始讲解具体题⽬，没有接触过回溯

法的同学刚学起来有点看不懂很正常，后⾯和具体题⽬结合起来会好⼀些。

相信很多⼩伙伴刷题的时候⾯对⼒扣上近两千道题⽬，感觉⽆从下⼿，我花费半年时间整理了

Github项⽬：「⼒扣刷题攻略」https://github.com/youngyangyang04/leetcode-master。

⾥⾯有100多道经典算法题⽬刷题顺序、配有40w字的详细图解，常⽤算法模板总结，以及难点视

频讲解，按照list⼀道⼀道刷就可以了！star⽀持⼀波吧！