回溯算法

回溯算法(back tracking)是一种类似尝试算法，按选优条件向前搜索，主要是在搜索尝试过程中寻找问题的解，以达到目标，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。换句话说，找到一条路往前走，能走就继续往前，不能走就算了，掉头换条路。相对于动态规划，这部分的内容相对于简单些。

回溯的处理思想，和枚举搜索有点类似，通过枚举找到所有满足期望的值。为了有规律地枚举所有的解，可以把问题拆解为多个小问题。每个小问题，我们都会面对一个岔路口，选择一条发现此路不通的时，就往回走，走到另一个岔路口。

本章节分为 2 个部分，选取了比较经典的算法题，希望可以帮助到同学们学会解决回溯相关的算法题。

• Part 1

  • 括号生成

  • 子集

  • 电话号码的字母组合

• Part 2

  • 全排列

  • 单词搜索