# 第 7 节 回溯算法视频讲解以及练习列表
下面提供一些我做过的「回溯」算法的问题，以便大家学习和理解「回溯」算法。
# 视频题解列表
# 题型一：排列、组合、子集相关问题
通过这些问题理解回溯算法的思想，回溯算法的知识点讲解在「力扣」第 46 题的视频题解和文字题解。
回溯就是用深度优先遍历的方式去搜索 树（图）的所有解。深度优先遍历有很明显的递归结构。
提示：这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用
used数组，有的时候设置搜索起点begin变量，理解状态变量设计的想法。
做对下面这些问题的技巧：
- 画图；
- 理解深度优先遍历与递归；
- 多调试。
- 第 47 题提示：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；
- 第 60 题提示：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；
- 第 90 题提示：剪枝技巧同 47 题、39 题、40 题。
# 题型二：字符串上的回溯问题
重点理解：由于字符串每次都生成新字符，无须状态重置。
提示：字符串的问题的特殊之处在于，字符串的拼接生成新对象，因此在这一类问题上没有显示「回溯」的过程，但是如果使用
StringBuilder拼接字符串就另当别论。在这里把它们单独作为一个题型，是希望朋友们能够注意到这个非常细节的地方。
第 22 题提示：这道题广度优先遍历也很好写，可以通过这个问题理解一下为什么回溯算法都是深度优先遍历，并且都用递归来写。
# 题型三：Flood Fill
Flood 是「洪水」的意思，Flood Fill 直译是「泛洪填充」的意思，体现了洪水能够从一点开始，迅速填满当前位置附近的地势低的区域。类似的应用还有：PS 软件中的「点一下把这一片区域的颜色都替换掉」，扫雷游戏「点一下打开一大片没有雷的区域」。
下面这几个问题，思想不难，但是初学的时候代码很不容易写对，并且也很难调试。我们的建议是多写几遍，忘记了就再写一次，参考规范的编写实现（设置 visited 数组，设置方向数组，抽取私有方法），把代码写对。
| 题号 | 链接 | 题解 |
|---|---|---|
| 79 | 单词搜索 (opens new window)（中等） | 文字题解 (opens new window) |
| 200 | 被围绕的区域 (opens new window)（中等） | |
| 130 | 被围绕的区域 (opens new window)（中等） | |
| 733 | 733. 图像渲染（Flood Fill，中等） (opens new window) |
说明：以上问题都不建议修改输入数据，设置 visited 数组是标准的做法。可能会遇到参数很多，是不是都可以写成成员变量的问题，面试中拿不准的记得问一下面试官
# 题型四：一些游戏问题
回溯算法是早期简单的人工智能，有些教程把回溯叫做暴力搜索，但回溯没有那么暴力，回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题，解决它们有一定的难度，大家可以尝试一下。
| 序号 | 题目序号 | 题解 |
|---|---|---|
| 51 | N 皇后 (opens new window)（困难） | 文字题解 (opens new window) |
| 37 | 解数独 (opens new window)（困难） | |
| 529 | 扫雷游戏 (opens new window)（中等） | 文字题解 (opens new window) |
| 488 | 488. 祖玛游戏（困难） (opens new window) |
说明：
- 第 51 题：经典问题，掌握「空间换时间」技巧；
- 第 529 题：寻找连通分量。DFS 和 BFS 均可；
- 第 488 题：很难，可以不做。
请大家做了一些回溯算法的问题以后顺便思考一下：深度优先遍历、递归、栈，它们三者的关系，我个人以为它们背后统一的逻辑都是「后进先出」。完成练习有助于我们深刻理解算法思想，我们加油！
作者：liweiwei1419 链接：https://suanfa8.com/backtracking/practice 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。