回溯算法

本质与框架

回溯算法本质上就是一种纯暴力穷举算法，复杂度一般都很高。抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。

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

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

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

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前做选择，在递归调用之后撤销选择，特别简单。

多叉树回溯遍历 vs 多叉树DFS遍历

对于回溯算法关联的那棵多叉树，其遍历框架是这样：

void traverse(TreeNode root) {
    for (TreeNode child : root.childern) {
        // 前序位置需要的操作
        traverse(child);
        // 后序位置需要的操作
    }
}

显然，我们知道多叉树 DFS 遍历框架的前序位置和后序位置应该在 for 循环外面，而在回溯算法中却跑到了 for 循环里面。

• DFS 遍历：关注点在节点

  void traverse(TreeNode root) {
      if (root == null) return;
      printf("进入节点 %s", root);
      for (TreeNode child : root.children) {
          traverse(child);
      }
      printf("离开节点 %s", root);
  }

• 回溯遍历：关注点在树枝

  void backtrack(TreeNode root) {
      if (root == null) return;
      for (TreeNode child : root.children) {
          // 做选择
          printf("从 %s 到 %s", root, child);
          backtrack(child);
          // 撤销选择
          printf("从 %s 到 %s", child, root);
      }
  }