13_backtrack

回溯算法

回溯算法和二叉树的 DFS 类似，本质上是一种暴力穷举算法。

抽象地说，解决一个回溯问题，实际上就是遍历一颗决策树的过程，树的每个叶子节点存放着一个合法答案。

我们把整棵树遍历一遍，把叶子节点上的答案全部收集起来，就能得到所有的合法答案。

站在回溯决策树的一个节点上，你只需要思考三个问题：

路径：那些已经做出的选择
选择列表：就是你当前可以做的选择
结束条件：到达决策树的底层，无法再做选择的条件

代码方面，回溯算法的基本框架是：

result = make([][]int, 0, 16)

func backtrace(选择列表, 路径) {
  if 满足结束条件 {
    result = append(result, path)
    return
  }
  for 选择 := range 选择列表 {
    做出选择
    backtrace(路径, 选择列表) // 或者叫 待选择列表
  }
}