回溯算法

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

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

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

  • Part 1

    • 括号生成

    • 子集

    • 电话号码的字母组合

  • Part 2

    • 全排列

    • 单词搜索