21. 回溯

0 - 算法, 0.0 - 算法模版 本文总阅读量次

正文

回溯（Backtracking）是一种深度优先搜索（DFS）的特殊形式，主要用于解决“排列、组合、切割、子集”等问题。它的核心在于试探与撤销。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
fun backtrack(path: MutableList<T>, options: List<T>) {
    // 1. 终止条件：满足特定的结束条件
    if (isFinished(path)) {
        // 记得拷贝结果 (deep copy)，否则最终返回的列表都是空的
        res.add(ArrayList(path))
        return
    }

    // 2. 遍历候选列表
    for (option in options) {
        // 剪枝：过滤掉不符合条件的路径
        if (!isValid(option, path)) continue

        // 3. 做选择
        path.add(option)

        // 4. 递归进入下一层决策树
        backtrack(path, nextOptions)

        // 5. 撤销选择：回溯的核心步骤
        path.removeAt(path.size - 1)
    }
}

使用说明

  1. 核心步骤：

    • 路径：记录已经做出的选择。
    • 选择列表：当前可以做的选择。
    • 结束条件：到达决策树叶子节点，结束递归。

  2. 核心技巧：

    • 深度优先遍历：先从根节点出发，一直走到叶子节点。
    • 状态重置：在递归返回时，必须将当前节点的状态重置（撤销选择），以便在下一次循环中尝试其他路径。
    • 深拷贝：在保存结果时，必须使用 ArrayList(path)。

  3. 常见变形：

    • 排列问题：需要使用 used 数组记录已选元素。
    • 组合/子集问题：通常需要一个 startIndex 来控制搜索范围，避免重复。
    • 剪枝优化：通过对数组预排序或提前退出循环来极大提升效率。

  4. 注意点：

    • 回溯算法的时间复杂度通常很高（指数级），必须结合题目特点进行剪枝。
    • 注意处理重复元素（如“组合总和 II”）。
0 - 算法, 0.0 - 算法模版