回溯算法 | newrain-zh博客

type

status

date

slug

summary

一、理解回溯

回溯是一种解决问题的算法技术，它涉及尝试不同的选项逐步找到解决方案，如果它们导致死胡同，则撤销他们。它通常需要他所多种可能性来解决问题，例如在迷宫中寻找路径或解决数独等谜题，算法会回溯到一个决策点并探索不同的路径，直到找到解决方案或用尽所有可能性。

理解回溯的前提是递归+链式结构（或者说树结构）+DFS，通常来说回溯能解决的问题都可以抽象成一个空间状态树，每个节点就是就是选择的元素和状态，路径就是保存每个选择的节点。

💡

hints:

这里总结解题思路：

解决回溯问题需要从以下几个方面考虑 1. 选择的列表是否要排序（正排序或倒排序）。 2. 收集的正确结果需要哪些条件。 3. 如何选择元素以及选择的元素是否要满足某种条件，才选择。 4. 选择元素的时候是否需要去重。 5. 回溯时，撤销的状态是否只有路径。

6. 考虑下一层逻辑（其它的交给归纳法）

回溯三部曲中有描述：代码回想录 1. 确认方法参数 2. 确认终止条件 3. 确认本层逻辑

回溯三问：灵神 1. 如何收集正确元素 2. 本层逻辑具体是什么 3. 下一层的逻辑是什么样的

学习回溯算法最好的入门示例就是编写一个树的路径问题。尝试画出状态空间树以及运行过程，可以为回溯算法打好基础。

核心逻辑：

递归 + 剪枝：通过递归生成所有可能的候选解，并通过条件剪枝（提前终止无效路径）。

状态恢复：在递归返回时撤销当前选择（如移除已添加的元素），避免状态污染。

适用场景：

回溯算法适用于许多搜索问题，包括但不限于：

组合问题：N个数里面按一定规则找出k个数的组合。

排列问题：N个数按一定规则全排列，有无重复数的排列。

子集问题：一个N个数的集合里面的所有子集。

切割问题：一个字符串按一定规则有几种切割方式。

棋盘问题：N皇后、解数独等等。

💡

hints:

并不是所有的回溯都是使用该模板，但是可以参考模板体现的思路。

状态空间树（state space Tree）

状态空间树是计算机科学中用于系统化的描述问题所有可能解空间的属性结构模型。它通过树的形式展先问题求解过程中所有可能的决策路径和状态变化，是回溯算法、分支限界等搜索算法的核心工具。

核心概念

节点

根节点：初始状态（未做任何决策的状态）

中间节点：部分决策后的中间状态

叶子节点：完整解或无法继续扩展的无效状态

边（分支）

表示父节点到子节点的决策动作，例如在八皇后问题中，每个分支代表在某一行的某个位置放置皇后

路径

从根节点到叶子节点的路径，对应一个完成的候选解或无效尝试。

二、回溯算法的特点

尝试发现解：通过试错的方式尝试分步去解决一个问题。

深度优先：它会尽可能深地搜索解的空间树，直到找到一个可能的解或者遍历所有的解。

剪枝：在遍历过程中，发现当前路径不可能是一个解时，就放弃这条路径，返回上一步（或上几步），尝试其他的选项，这个过程称为剪枝。

递归前的选择：在进入递归之前做出选择。

递归后的撤销：在从递归返回后撤销前面做的选择，以保证每次递归返回后环境与之前相同。

回溯算法的核心是从选择列表中做出选择，递归调用，然后撤销选择。通过这个过程，遍历决策树的所有分支，寻找所有的解。回溯算法的效率可能不是特别高，因为它是一种暴力搜索方法，在实际应用中常常需要结合剪枝策略来提高搜索效率。

三、优化技巧与常见陷阱

1. 剪枝优化

提前终止无效分支：例如在组合问题中，若当前路径和已超过目标值，直接返回。

记忆化剪枝：缓存已计算的状态（如使用哈希表记录已访问路径）。

2. 去重技巧

排序 + 跳过重复元素：例如在子集II中，排序后通过 nums[i] == nums[i-1] 跳过重复元素。

哈希表记录路径：适用于无法排序的场景（如排列问题）。

总结如下

组合去重	排序 + for (int i = start; i < n; i++)
排列不去重	for (int i = 0; i < n; i++)
元素可重复使用	backtrack(..., i, ...)
元素只能使用一次	backtrack(..., i + 1, ...)

3. 避免常见错误

忘记回溯撤销状态：如修改全局变量后未恢复。

递归终止条件错误：如遗漏终止条件导致无限递归。

索引越界：在组合问题中注意递归起始位置（如从 start 开始遍历）。

三、递归与回溯

通常回溯都是用递归去实现的，注意这里说的通常，偶尔也可以使用BFS。

递归通常和循环都能互转，但是有些回溯问题使用循环的思路去解决会异常困难。

递归	回溯
递归并不总是需要回溯	回溯始终使用递归来解决问题
递归函数通过调用自身的副本并解决原始问题的较小子问题来解决特定问题。	每一步的回溯都消除了那些无法给我们解决方案的选择，并继续进行那些有可能将我们带到解决方案的选择。
递归本身是回溯的一部分，编写起来更简单。	回溯的实现相对复杂。
递归的应用是树和图遍历、河内塔、分而治之算法、归并排序、快速排序和二进制搜索。	回溯的应用是 N Queen 问题、迷宫中的老鼠问题、Knight's Tour 问题、数独求解器和图形着色问题。

四、相关习题

阶段1：基础模板与经典问题

必练题目：

全排列（LeetCode 46. Permutations）：掌握无重复元素的排列生成。

子集（LeetCode 78. Subsets）：生成所有可能的子集。

组合总和（LeetCode 39. Combination Sum）：允许重复选择元素的组合问题。

电话号码的字母组合（LeetCode 17. Letter Combinations）：多分支递归的典型应用。

练习目标：

熟悉回溯模板：初始化路径 → 递归选择 → 剪枝 → 回溯撤销。

理解如何通过参数传递状态（如当前路径、起始索引）。

阶段2：去重与剪枝优化

必练题目：

全排列 II（LeetCode 47. Permutations II）：含重复元素的排列去重。

子集 II（LeetCode 90. Subsets II）：含重复元素的子集生成。

组合总和 II（LeetCode 40. Combination Sum II）：元素不可重复使用的组合问题。

复原IP地址（LeetCode 93. Restore IP Addresses）：分割问题中的剪枝条件设计。

练习目标：

掌握如何通过排序和条件判断实现去重（如 if (i > start && nums[i] == nums[i-1])）。

学习剪枝优化（如提前终止不符合条件的分支）。

阶段3：复杂问题与综合应用

必练题目：

N皇后问题（LeetCode 51. N-Queens）：经典棋盘类问题。

解数独（LeetCode 37. Sudoku Solver）：二维回溯的复杂应用。

分割回文串（LeetCode 131. Palindrome Partitioning）：结合动态规划预处理回文子串。

单词搜索（LeetCode 79. Word Search）：二维矩阵中的路径搜索。

练习目标：

处理复杂状态（如二维棋盘、矩阵路径）。

结合其他算法（如动态规划、位运算）优化回溯效率。

六、刷题笔记

组合问题

例如[a,b,c] [d,e,f] [g,h,i] 前后字母能有多少种可能

组合问题的编程种要注意的问题是先将需要组合的第一个元素加入列表

例如以上问题，要先将a ,b ,c 加入一个列表。

List = [a,b,c]，然后遍历这个 list，去组合所有的可能。

组合总和问题

图解地址

数字组合

给定一个候选数字的集合 candidates 和一个目标值 target。找到 candidates 中所有的和为 target 的组合。

在同一个组合中, candidates 中的某个数字出现次数不限。

所有数值 (包括 target ) 都是正整数.

返回的每一个组合内的数字必须是非降序的.

返回的所有组合之间可以是任意顺序.

解集不能包含重复的组合.

子集问题（TODO）

N皇后问题

题目梳理

解题思路

如何计算对角线坐标

主对角线（↘）：从左上到右下，满足 row - col 相等

主对角线，每行下移一格，列也右移一格 row++,col++ → r-c不变(行-列)

副对角线（↙）：从右上到左下，满足 row + col 相等

每行下移一格，列左移一格（r++, c–-）→ r + c 不变 (行+列)

↘ 主对角线：行 - 列相等 ↙ 副对角线：行 + 列相等

如何判断两个位置是否在对角线上

例如坐标示例 [2,1] 的位置，判断 [1,0] 、[2,1] 是否在同一对角线

[1,0] = 1-0 = 1

[2,1] = 2-1 = 1

结果都为 1 说明处于主对角线上。