代码随想录算法训练营第22天｜回溯算法Part01

回溯算法本质是一种暴力搜索的方法：它通过不断地尝试各种可能的解决方案， 并在发现不可行的解时回退到之前的状态，继续尝试其他的路径，从而确保枚举出所有可能的答案。

回溯算法的工作原理

回溯算法可以抽象为一个 N 叉树的遍历过程。 每一个节点代表一种可能的选择路径，而整棵树覆盖了所有可能的解决方案。

一般而言：

• 树的宽度：代表在某一层我们面临的选择个数， 通常通过 for 循环实现；
• 树的深度：对应递归的层数，即每走一步就深入下一层；

回溯算法的基本流程如下：

1. 从根节点出发，做出一个选择；
2. 如果当前选择仍可能构成解，就继续向下探索；
3. 如果遇到不满足条件的情况，立即回溯，撤销上一步选择；
4. 如果所有路径都试过了，还没解，说明无解；
5. 如果找到了一个满足条件的解，将其加入结果集。

这个过程可以用递归来实现。在递归函数中，需要明确以下三个关键点：

• 递归函数的参数和返回值
• 递归的终止条件
• 单层搜索的逻辑

回溯算法范式

在回溯题目中，我们可以总结出一个范式：

function backtrack(路径, 选择列表, ...args) {
    if (终止条件) {
        // 记录结果
        return;
    }

    for (let 选择 of 选择列表) {
        // 做出选择
        路径.push(选择);

        // 递归调用
        backtrack(路径, 新的选择列表);

        // 回溯，撤销选择
        路径.pop();
    }
}

关键点说明：

• 路径 表示当前选择的集合，通常是一个数组，用于记录搜索过程；
• 选择列表 表示当前层可供选择的元素集合；
• 回溯过程始终遵循“做出选择 → 递归深入 → 撤销选择”这一范式；
• 回溯的核心并不是“剪枝”，而是“尝试 + 回退”的机制，剪枝是优化，而非必要条件；

从遍历角度看，for 循环负责 横向遍历（枚举当前层所有可能选择）， 递归负责 纵向推进（深入每一种路径的下一层）。

回溯法适用的问题类型

回溯算法主要应用于“在集合中递归查找子结构”的问题。常见的五类问题如下：

1. 排列问题 给定 N 个元素，找出它们的所有排列方式。 排列强调顺序，[1, 2] 和 [2, 1] 被视为不同结果。

2. 组合问题 给定 N 个元素，从中选出 K 个元素组成一个组合集合。组合不强调顺序。

3. 子集问题 给定一个集合，找出它的所有子集，包含空集和全集。

4. 切割问题 给定一个字符串，按某种规则进行切割，使得每个切割片段满足特定要求（如回文）。

5. 棋盘问题 包括 N 皇后、解数独、迷宫路径等，通常涉及二维空间中的递归回溯搜索。

组合与排列的关键区别在于是否考虑顺序。组合是无序的，排列是有序的。 例如：{1, 2} 与 {2, 1} 在组合中视为同一组，在排列中是两组不同结果。

小结

回溯算法是一种通过不断尝试和撤销来遍历所有可能解空间的暴力搜索策略。 它虽然效率不高，但在某些只能枚举的问题上是唯一可行的解法。

掌握回溯算法的关键在于：

• 明确递归三要素：参数、终止条件、单层逻辑；
• 学会将问题抽象为树形结构，并识别“横向选择”和“纵向递归”的过程；
• 熟练掌握通用模板，在模板基础上按题意做定制化修改；
• 正确认识回溯的本质是穷举搜索，而非高效算法；

通过不断练习不同类型的回溯问题，可以建立起对这类题型的直觉和模型理解， 从而在面对组合类搜索时迅速构造出合理的解法框架。