回溯

相关源文件

• README.md

回溯是一种系统化的算法技术，用于寻找计算问题的解决方案，特别是在约束满足场景中，解决方案是逐步构建的。本文档介绍了回溯算法的核心原理、实现模式和问题解决策略，这些内容在 leetcode-master 仓库中有所呈现。

有关相关算法，例如动态规划方法，请参见 动态规划，有关有时使用回溯的基于树的问题，请参见 二叉树。

来源： README.md225-248

回溯的核心原则

回溯是一种算法范式，它尝试不同的解决方案，直到找到一个“有效”的解决方案。它逐步构建解决方案的候选，并在确定候选无法 dẫn đến 一个有效解决方案时，立即放弃该候选（“回溯”）。

回溯算法的关键特征包括：

1. 增量构建：解决方案是逐步构建的。
2. 约束检查：在每一步验证有效性。
3. 回溯机制：能够撤销选择并尝试其他选项。
4. 穷举搜索：对解空间进行完整探索（通常可视化为一棵树）。

当回溯算法能够在过程早期消除大部分搜索空间时，它们尤其高效。

来源： README.md227-228

回溯框架

通用结构

本仓库中的所有回溯算法都遵循一致的实现模式，可以将其可视化为：

问题分类

仓库中的回溯问题根据其问题结构进行组织分类。

来源： README.md227-248

实现模板

仓库中回溯的核心实现遵循标准递归模板：

1. 定义问题状态和结果容器。
2. 定义一个带有表示当前状态的参数的递归函数。
3. 检查终止的基本条件。
4. 循环遍历当前状态下的可用选择。
5. 对于每个选择：
   • 做出选择。
   • 用更新后的状态递归地探索。
   • 撤销选择（回溯）。
6. 返回结果。

此模式在仓库的所有回溯问题中都可以观察到。

来源： README.md227-248

关键问题类别

组合问题

组合问题涉及从集合中选择特定数量的元素，其中选择的顺序无关紧要。该仓库涵盖了：

问题	描述	难度	关键技术
77. 组合	生成1到n的数字的所有可能的k个组合。	中等	基本组合模板
77. 组合（优化）	组合问题的优化版本。	中等	剪枝
216. 组合总和 III	查找和为n的所有k个数字的有效组合。	中等	带约束的组合
39. 组合总和	查找所有和为目标值的候选组合。	中等	元素可无限使用
40. 组合总和 II	查找所有和为目标值的组合（输入中有重复项）。	中等	跳过重复项

来源： README.md228-234

子集问题

子集问题涉及生成给定集合的所有（或特定）子集。

问题	描述	难度	关键技术
78. 子集	生成集合的所有可能子集。	中等	基本子集生成。
90. 子集 II	生成所有可能的子集（输入中有重复项）。	中等	跳过重复项
491. 递增子序列	查找所有递增子序列。	中等	路径依赖选择。

来源： README.md237-240

排列问题

排列问题涉及生成顺序很重要的排列。

问题	描述	难度	关键技术
46. 排列	生成所有可能的排列。	中等	已使用/未使用元素跟踪。
47. 排列 II	生成所有可能的排列（有重复）。	中等	跳过重复项

来源： README.md241-242

分割问题

分割问题涉及将结构划分为有效的片段。

问题	描述	难度	关键技术
131. 回文分割	将字符串分割，使得每个子串都是回文串。	中等	子串验证。
93. 复原 IP 地址	复原所有可能的有效 IP 地址。	中等	段验证。

来源： README.md235-236

复杂应用

该仓库涵盖了高级回溯应用：

问题	描述	难度	关键技术
332. 重构行程	重构航班行程。	中等	带回溯的图遍历。
51. N皇后	在N×N棋盘上放置N个皇后。	困难	约束检查。
37. 数独求解器	求解数独谜题。	困难	约束传播。

来源： README.md245-247

回溯决策树

回溯中的决策过程可以可视化为遍历一棵树。

来源： README.md227-228

处理常见复杂性

1. 避免重复

当输入包含重复项时，需要额外的技术来避免重复的解决方案。

1. 排序输入：许多问题首先对输入数组进行排序。
2. 跳过相邻重复项：在处理同一层级的选择时。
3. 路径验证：检查是否已见过某个特定的组合/路径。

来源： README.md241-242 README.md244

2. 剪枝搜索空间

高效的回溯实现可以减少不必要的探索。

1. 提前终止：放弃不能 dẫn đến 有效解决方案的路径。
2. 基于约束的剪枝：跳过会违反问题约束的选择。
3. 增量验证：在每一步验证有效性，而不是仅在最后。

来源： README.md229-231

与其他算法的关系

来源： README.md225-248

学习路径整合

回溯是介于基本数据结构操作和更高级算法技术之间的桥梁。

来源： README.md152-166

总结

回溯是一种强大的算法范式，它逐步构建必须满足约束条件的问题的候选。该仓库系统地介绍了回溯问题，从基本的组合问题开始，到 N 皇后和数独求解器等复杂应用。

掌握回溯的关键在于理解：

1. 递归模板结构。
2. 如何在递归期间定义和管理状态。
3. 何时以及如何应用剪枝技术。
4. 特定于问题的约束和验证。

遵循仓库中推荐的学习顺序，可以为回溯技术奠定坚实的基础，这些技术可以应用于广泛的算法挑战。

来源： README.md227-248