陈恒承

回溯

回溯算法是对树形或者图形结构执行一次深度优先遍历，实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。
深度优先遍历有个特点：当发现已不满足求解条件时，就返回，尝试别的路径。此时对象类型变量就需要重置成为和之前一样，称为「状态重置」。

许多复杂的，规模较大的问题都可以使用回溯法，有「通用解题方法」的美称。实际上，回溯算法就是暴力搜索算法，它是早期的人工智能里使用的算法，借助计算机强大的计算能力帮助我们找到问题的解。

模版

result = []
function backtrack(路径,/*others args ...*/){
     // 这里终止条件要说一下，一般是路径的长度
     if (满足结束条件){
         result.add(路径)
        return
     }

     for 选择 in 选择列表:
         //做选择
         backtrack(路径,/* others args */)
         // 撤销选择
}

backtrack([])
/*
   result： 存放求解的数组

   路径: 一般而言，都是从空数组开始进行构造

   backtrack（...args） 定义的回溯函数

   递归结束的条件： 这个非常重要，说明我们已经构建到需要的组合了，就需要加入 result 中

   for 选择 in 选择列表:

   这里面做选择，从选择列表中选择元素，加入 路径中，如下一个模式:
         path.push(val)
         backtrack(path)
         path.pop()  //最后取消选择的元素
*/

需要注意的点

• 递归的结束条件，构造解
• 选择列表时，该怎么选择元素， backtrack（路径,选择元素的索引)
• 该怎么撤销
• 循环体的遍历

学习资源

• 回溯算法套路详解 - labuladong 的文章 - 知乎
  https://zhuanlan.zhihu.com/p/93530380

回溯问题的特性

探索,尝试，n 种方案

排列，组合，多解 ,比如- 求子集，ip 地址复原,排列组合,n 个数字二叉树生成，n 皇后,图的搜索遍历，

或者是求多少种解决方案的个数
等等，可以观察看问题的求解事多种组合。

高级别的回溯 (未掌握)

• 选择，递归条件都很难构造