简述

回溯是递归的副产品,只要有递归就会有回溯。

因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。

适合回溯解决的问题

回溯法,一般普遍用于解决如下几种问题:

  • 组合问题

    • N个数里面按一定规则找出k个数的集合

    例题: 77. 组合 17.电话号码的字母组合 39.组合总和 40.组合总和II 216.组合总和III

  • 切割问题

    • 一个字符串按一定规则有几种切割方式

    例题: 131. 分割回文串 93. 复原IP地址

  • 子集问题

    • 一个N个数的集合里有多少符合条件的子集

    例题: 78. 子集 90.子集II 491. 递增子序列 (不完全是,但解法很像)

  • 排列问题

    • N个数按一定规则全排列,有几种排列方式

    例题: 46. 全排列 47. 全排列 II

  • 棋盘问题

    • N皇后,解数独等等

    例题: 51. N皇后 37. 解数独

树形结构

回溯法是一种经常被用在 深度优先搜索(DFS)和 广度优先搜索(BFS)的技巧。

其本质是:走不通就回头。

因此, 回溯法解决的问题都可以抽象为树形结构,同样的道理,当发现问题可以抽象为树形结构的时候,要能够想到回溯法。

树形结构必然具有特定的属性: 树宽 和 树高

  • 因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。
  • 递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

回溯的实现过程 - 基础版

回溯法的本质是: 走不通就回头。那么怎么回头,而且确保回头之后不会重新走这条路,就是在使用回溯算法需要首先思考的。

纯暴力回溯的实现过程

回溯法的搜索过程基本可以概括为以下四步:

  1. 构造空间树
  2. 进行横向遍历: 同一层所有元素
    3. 对于每一个节点来说,需要进行以下操作:
    • 如果达到终止条件,输出结果
    • 否则不符合条件,向下搜索,到底了则转而搜索另一条链
    关键点: 回溯,撤销当前链的处理结果

代码模板 (基础版)

void backtracking(参数){
  if (终止条件){
      存放结果;
      return;
  }
  for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)){      # 横向遍历
      处理节点;
      backtracking(路径,选择列表); // 递归                    # 纵向遍历
      回溯,撤销处理结果
  }
}

剪枝优化

优化回溯算法只有剪枝一种方法

剪枝的核心目的,说白了就是减少没必要的搜索空间,从而减少时间和空间的复杂度。

因此,剪枝的精髓就在于: 在纵向遍历的过程中是否可以敏锐地发现提前终止的时机。

以组合问题为例

  • 我们试图通过回溯算法,从N个数里面按一定规则找出k个数的集合

在这个搜索过程中,当搜索执行到了空间树某一层的某一个节点时,剪枝算法发现这个起点到集合终止之间的元素已经不够题目要求的k个元素了,就没有必要搜索了。

假设这个节点之后还有M层的子树,那么这一次剪枝就可以替我们减少O(2^M)的复杂度。

代码模板 (剪枝版)

void backtracking(参数) {
  if (终止条件) {
    存放结果;
    return;
  }
  for i in range(start_index, len(nums))  {      # 横向遍历
      if ( i 满足剪枝条件):
        continue
      处理节点;
      backtracking(路径,选择列表); // 递归         # 纵向遍历
      回溯,撤销处理结果
  }
}

⭐️去重优化

剪枝和去重

不是说回溯算法唯一的优化方法是剪枝么?那去重是干嘛?

剪枝是针对代码层次的优化
  • 剪枝是针对回溯算法整体上的通用优化方法,可以直接写到代码模板里。在任何情况下,回溯算法都是可以使用剪枝的方法减少搜索空间,但是很多情况下能够减少的搜索空间较为有限。
去重是解题思路层次的优化
  • 所谓去重,其实就是确保使用过的元素不能重复选取。 实现起来有一定难度,因为往往无法分清楚到底是从(横向,纵向)中的哪个维度避免重复。
  • 已知回溯法所解决的问题都可以抽象为树形结构,那么“使用过”在这个树形结构上是有两个维度的,纵向维度是同一树枝上使用过,横向维度是同一树层上使用过。
  • 所以去重优化要解决的第一个问题就是,我们关注的是要同一树层上使用过,还是同一树枝上使用过呢?
  • Leetcode 40. 组合综合II为例,我们发现元素在同一个组合内是可以重复的,怎么重复都没事,但两个组合不能相同。即给定原始数组candidates = [1, 1, 2], target = 3的情况下(方便起见candidates已经排序了)当第一个树枝上使用了index为0的1时,不影响我们在同一树枝上继续使用index为1的1,但是同一层如果再次使用 index为0的1,则必定出现重复的情况。
  • 所以我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重。

⭐️树枝去重

树枝:从根节点 到 某一个叶子节点的路径

为了避免原始数组中,同一个位置的元素(考虑到可能存在重复值)在路径中被反复使用,需要定义一个全局变量来记录哪一个元素被使用了,该变量按惯例通常被称为used。

used = [0 for _ in range (len(nums))]

void backtracking(参数) {
  if (终止条件) { 
    … 略过 
  }
  for i in range (start_index, len(nums))  {      # 横向遍历
    if ( i 满足剪枝条件) { 
      continue 
    }
    if (used[i] == 0) { 
      continue 
    }
    处理节点;
    used[i] = 1
    backtracking(路径,选择列表); // 递归            # 纵向遍历
    回溯,撤销处理结果
    used[i] = 0
  }
}

⭐️树层去重

树层去重的方式与树枝去重类似,同样可以通过定义一个used变量来记录。

但是区别在于,要控制同一个树层的元素不重复,需要定义的是局部变量,而不是全局变量。

void backtracking(参数) {
  if (终止条件) { 
    … 略过 
  }
  
  used = [0 for _ in range (len(nums))]

  for i in range (start_index, len(nums))  {      # 横向遍历
    if ( i 满足剪枝条件) { 
      continue 
    }
    if (used[i] == 0) { 
      continue 
    }
    处理节点;
    used[i] = 1
    backtracking(路径,选择列表); // 递归            # 纵向遍历
    回溯,撤销处理结果
    used[i] = 0
  }
}

在很多Leetcode解法中,会发现有人习惯于使用set代替数组进行去重,但是值得注意的是使用used数组去重 和 使用set去重 两种写法存在较大性能差异:

使用set去重的版本相对于used数组的版本效率都要低很多。而使用used数组在时间复杂度上几乎没有额外负担!

组合和切割问题的解法

组合问题

  • 时间复杂度:O(2^n)
  • 空间复杂度:O(n)
  • 组合问题其实就是一种子集的问题,所以组合问题最坏的情况,也不会超过子集问题的时间复杂度。而子集问题因为每一个元素的状态无外乎取与不取,所以时间复杂度为O(2^n)
  • 递归深度为n,所以系统栈所用空间为O(n),每一层递归所用的空间都是常数级别,注意代码里的result和path都是全局变量,就算是放在参数里,传的也是引用,并不会新申请内存空间,最终空间复杂度为O(n)

组合问题在回溯问题中相对简单,也比较具有代表性,因此回溯的基础模板和剪枝模板完全可以解决普遍意义上的组合问题,在这里不再重复。

而组合问题本身的一大难点,在于如何避免无序状态下的重复,以Leetcode组合问题为例。

第一层,取2的时候,需要把1从candidate中删除,否则会引入重复的风险,3同理需要将2删除。

for i in range(start_index, len(nums))  {      # 横向遍历
  处理节点;
  backtracking(路径,选择列表); // 递归           # 纵向遍历
  回溯,撤销处理结果
}

切割问题

  • 时间复杂度:O(2^n), 与组合问题一致
  • 空间复杂度:O(n), 与组合问题一致

切割问题的难点,在于如何模拟切割线,以及判断切割问题中如何终止递归。本身的解法非常类似组合问题。 能够想到用求解组合问题的思路来解决 切割问题本题就成功一大半了。

排列和子集问题的解法

排列问题

  • 时间复杂度:O(n!)
  • 这个可以从排列的树形图中很明显发现,每一层节点为n,第二层每一个分支都延伸了n-1个分支,再往下又是n-2个分支,所以一直到叶子节点一共就是n!。
  • 空间复杂度:O(n),和组合问题同理。

组合和排列的核心区别,在于组合不关注顺序,而排列在乎顺序,[1, 2] 和 [2, 1]两个数组,在组合问题中是同一组合,而在排列问题中是不同的排列。

因此,解组合问题中需要用到的start_index参数在排列问题中可以略去。

for i in range(0, len(nums))  {         # 横向遍历
  if ( i 满足剪枝条件):
    continue
  处理节点;
  backtracking(路径,选择列表); // 递归    # 纵向遍历
  回溯,撤销处理结果
}

子集问题

  • 时间复杂度:O(2^n)
  • 因为每一个元素的状态无外乎取与不取,所以时间复杂度为O(2^n)
  • 空间复杂度:O(n),与组合问题一致

子集问题和组合问题的核心区别,在于组合问题只需要采集叶子节点,而子集需要采集所有节点。

因此组合问题的终止条件往往是依据节点中元素的数量,而子集问题不需要终止。

if ( len(ans) == len(nums) ) {
  存放结果;
  return;
}

棋盘问题的解法

棋盘问题算是回溯算法中最巅峰的困难题了,同时也是人工智能领域的必修课。

传统意义上的棋盘类游戏,包括中国象棋、国际象棋、围棋、数独、五子棋,都是二维的棋盘,那么自然就得考虑到二维递归的可能性。

而不同的游戏规则会直接导致每一层分支的宽度,因此棋盘类解法的性能没办法统一评估。

以N皇后问题为例,虽然期盼乍一看是n * n的,但是根据N皇后的游戏规则可以发现,一行必有且仅有一个皇后,因此递归的深度其实只有n。所以比真正意义上的棋盘全搜索要简单一些。

分析可得:

  • 时间复杂度:O(n!) ,其实如果看树形图的话,直觉上是O(n^n),但皇后之间不能见面所以在搜索的过程中是有剪枝的,最差也就是O(n!)。
  • 空间复杂度:O(n),和子集问题同理

而解数独问题,则是标准的二维递归,分析可得:

  • 时间复杂度:O(9^m) , m是空格的数目。
  • 空间复杂度:O(n^2),递归的深度是n^2

不考虑问题本身的特性,二维棋盘的代码可以以下模板进行归纳

board = [
  [......],
  ……
]

void backtracking(i, j) {
  if (终止条件) { 
    … 略过 
  }
  for ( a in board(i, j)位置所有可能的action)  {      # 横向遍历
      if ( a 满足剪枝条件) { 
        continue 
      }
      处理节点;
      backtracking( i', j' )                       # 纵向遍历
      回溯,撤销处理结果
  }
}

# 最外层遍历所有可能的起点
for i in range( 0, len(board) ) {
  for j in range (0, len(board) ) {
      backtracking(i, j)
  }
}
#Tech
算法与数据结构 - 回溯篇
https://billyjojojobulidogithub.io/notes/Algorithm/backtracking/chinese/index.html
Author
Baocheng Wang
Posted on
July 25, 2024
Licensed under