回溯算法详解

Last renew: September 17, 2022 pm

回溯问题概述

注：本文仅为个人学习笔记，无任何版权。

注2: dfs与回溯之间并不是并列的关系，dfs是一种深度优先的遍历方法，而回溯是一种解决问题的手段。dfs可以有回溯，回溯也可以用dfs。

什么是回溯算法？

回溯法也可以叫做回溯搜索法，是一种搜索的方式。回溯是递归的副产品，有递归就会有回溯。

回溯法的效率

回溯法的性能如何呢？实际上不是什么高效的算法。因为本质是穷举。如果想要回溯法高效，可以增加一些剪枝的操作。但效率仍然一般，因为其本质就是穷举。

回溯法适合解决的问题

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等

注：组合和排列的区别是组合不强调元素顺序，排列强调元素顺序。

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度则构成了树的深度。

使用递归就要有中止条件，所以树的高度是有限的。

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考三个问题。

  1. 路径：也就是已经作出的选择。
  2. 选择列表：也就是你当前可以做的选择。
  3. 结束条件：也就是到达决策树底层，无法再做选择的条件。
1
2
3
4
5
6
7
8
9
10
11
result = []
public static backtrack(路径，选择列表):
  if (满足结束条件){
    result.add(路径);
    return;
  }
  for (选择 : 选择列表) {
     做选择 or 处理节点;
     backtrack(路径，选择列表); // 递归
     回溯，撤销选择;
  }

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

可以看出for循环就是横向的遍历，backtracking就是纵向遍历，这样就把这棵树全遍历完了。

这个框架的奥秘在哪里呢？我们来看两道例题：

1. 全排列问题

高中的排列组合数学题。对于n个不同的数，全排列共有n!个。

穷举全排列的方法？[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1]…..

可以按照这个逻辑画出一颗决策树。

只要从root遍历这棵树，记录路径上的数字，其实就是所有的全排列。

假如我们进行穷举走到了[2, x, y]的分叉，这时候2的含义就是[路径]，用于记录你已经做过的选择；

而[1]或[3]则是[选择列表]。表示你当前可以做出的选择；

[结束条件]就是遍历到树的底层，在这里就是选择列表为空的时候。

这时候可以看出，我们所定义的backtrack函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其[路径]就是一个全排列。

那么，如何遍历这棵树？

简单的二叉树遍历罢了，前序遍历 or 后序遍历。

1
2
3
4
5
6
void traverse(TreeNode root) {
  for (TreeNode child : root.children)
  //前序遍历需要的操作
    traverse(child);
  //后序遍历需要的操作
}

稍微回忆一下，前序遍历的代码会在进入某一个节点之前的时间执行，而后序遍历代码会在离开某个节点之后的那个时间点执行。

而就在刚才我们所述，[路径]和[选择]是每个节点的属性，函数在树上游走要正确维护节点的属性。所以我们应当在前序和后序两个位置选择不同的操作。

前序为做出选择，而后序为撤销选择。

1
2
3
4
5
6
7
8
for 选择 in 选择列表:
  #做选择
  将该选择从选择列表移除
  路径.add(选择) 
  backtrack(路径，选择列表)
  #撤销选择
  路径.remove(选择)
  将该选择再加入选择列表

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确的得到每个节点的选择列表与路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
List<List<Integer>> res = new LinkedList<>();

// 主函数，输入一组不重复的数字，返回他们的全排列
List<List<Integer>> permute(int[] nums) {
  // 记录路径
  LinkedList<integer> track = new LinkedList<>();
  backtrack(nums, track);
  return res;
}

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件: nums 中的元素全都在track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
  // 触发结束条件
  if (track.size() == nums.length) {
    res.add(new LinkedList(track));
    return;
  }
  
  for (int i = 0; i< nums.length; i++) {
    // 排除不合法的选择
    if (track.contains(nums[i]))
      continue;
    // 做选择
    track.add(nums[i]);
    // 进入下一层决策树
    backtrack(nums, track);
    // 取消选择
    track.removeLast();
  }
}

自此，我们就通过全排列问题了解了简单的回溯算法。当然，这个算法解决全排列并不高效，contains方法需要O(N)的时间复杂度。有更好的方法可以follow up

但不论怎样优化，只要符合回溯框架，时间复杂度都不可能低于O(N!)，因为穷举整棵树是无法避免的。一般回溯算法时间复杂度都很高。