跳转至

回溯法

回溯法本质上就是穷举法、暴力搜索，递归遍历整颗解答树，效率不高。

通常会在遍历时进行剪枝，提前排除掉不可能的情况，提高效率。

能解决的问题

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

模板

一般都用递归来实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void backtracking(/* 参数 */) {
    if (/* 终止条件 */) {
        // 存放结果
        return;
    }

    for (/* 本层集合中元素 */) {
        // 处理节点
        backtracking(/* 路径，选择列表 */); // 递归
        // 回溯，撤销处理结果
    }
}

一些剪枝方法

  • 求和问题中，一开始对所有数字的集合进行排序，然后如果当前的 sum 已经超过了目标值就直接剪枝。

    例题：39. 组合总和。

题目

一些还不错的题。