「回溯算法」专题 1：在树形问题中使用深度优先遍历
回溯法是解决很多算法问题的常见思想，甚至可以说是传统人工智能的基础方法。其本质依然是使用递归的方法在树形空间中寻找解。在这一章，我们来具体看一下将递归这种技术使用在非二叉树的结构中，从而认识回溯这一基础算法思想。
在解决二叉树的问题的中我们已经看到了递归算法的威力和有趣之处，也体会到了使用递归算法的痛点。当然，递归算法也绝不仅仅只是适用于二叉树问题的解决。从这一节开始，我们会在更多、更广义的问题上，使用递归算法。
递归算法还能够解决的一个典型问题，是具有树形结构的问题，当我们发现一个问题与一个更小的问题之间存在递归关系的时候，此时，递归关系呈现出来的就是一个树形结构。
为此，我们从一个比较简单的问题入手，介绍什么是树形问题。
回溯算法
- 回溯搜索算法就是在树形图上的深度优先遍历；
- 正因为「深度优先遍历」有「回退」的过程，才需要「状态重置」或者称「撤销选择」，这就是「回溯」的意思。
理解回溯算法的第一步是画出树形图。
参考的练习题在第 1 部分。
难点 1
理解「回溯」，倒不如把「回溯」理解成「深度优先遍历」，「回溯」只是现象，本质是 DFS
- 回溯算法本质上是遍历的算法，全程使用一份状态变量去搜索状态空间里的所有状态，是节约空间的；
- 深度优先遍历呈现「一条道走到底，不撞南墙」不回头的特点。
难点 2
「深度优先遍历」与「广度优先遍历」的联系与差别：
- 回溯算法本质上是遍历的算法，全程使用一份状态变量去搜索状态空间里的所有状态，是节约空间的；
- 深度优先遍历呈现「一条道走到底，不撞南墙」不回头的特点。
回溯法是解决很多算法问题的常见思想，甚至可以说是传统人工智能的基础方法。其本质依然是使用递归的方法在树形空间中寻找解。在这一章，我们来具体看一下将递归这种技术使用在非二叉树的结构中，从而认识回溯这一基础算法思想。
在解决二叉树的问题的中我们已经看到了递归算法的威力和有趣之处，也体会到了使用递归算法的痛点。当然，递归算法也绝不仅仅只是适用于二叉树问题的解决。从这一节开始，我们会在更多、更广义的问题上，使用递归算法。
递归算法还能够解决的一个典型问题，是具有树形结构的问题，当我们发现一个问题与一个更小的问题之间存在递归关系的时候，此时，递归关系呈现出来的就是一个树形结构。
为此，我们从一个比较简单的问题入手，介绍什么是树形问题。
