是暴力搜索 + 回退的一种方法。它的核心逻辑是：
-
尝试：往前走一步，做一个选择。
-
回退：如果走不通，就撤销选择，回到上一步。
-
继续尝试：换一条路，直到找到解或把所有可能性都试完。
特点：
-
本质：深度优先搜索（DFS）。
-
关键：用“剪枝”减少无效搜索，提高效率。
-
框架：尝试 → 判断 → 回退。
例子：
-
搜索问题：全排列、子集和、路径搜索。
-
约束问题： 皇后、数独、图着色。
-
优化问题：0-1 背包、旅行商问题、最大团。
优缺点：
-
优点：能找到所有解，思路清晰。
-
缺点：复杂度高，容易爆炸，需要剪枝或启发式策略。
| 名词 | 定义 |
|---|---|
| 解（solution） | 解是满足问题特定条件的答案，可能有一个或多个 |
| 约束条件（constraint） | 约束条件是问题中限制解的可行性的条件，通常用于剪枝 |
| 状态（state） | 状态表示问题在某一时刻的情况，包括已经做出的选择 |
| 尝试（attempt） | 尝试是根据可用选择来探索解空间的过程，包括做出选择，更新状态，检查是否为解 |
| 回退（backtracking） | 回退指遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态 |
| 剪枝（pruning） | 剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率 |