何时用回溯法？何时用普通 DFS？
要明确「何时用回溯法」「何时用普通 DFS」，核心是抓住目标导向和状态管理两个关键 —— 普通 DFS 侧重「无差别遍历 / 验证」，回溯法侧重「有目的试错找解」。以下是具体判断标准、场景和实例：
一、核心判断准则（先记这 3 点）
| 判断维度 | 用普通 DFS | 用回溯法 |
|---|---|---|
| 核心目标 | 遍历所有节点 / 路径，或验证某个属性（如连通性、路径存在） | 从解空间中找到所有 / 任一满足条件的解（如组合、排列、合法方案） |
| 是否需要「主动撤销状态」 | 无需（递归栈自然回溯，无持久化路径） | 必须（显式维护路径 / 选择状态，递归后恢复原状） |
| 是否需要剪枝 | 几乎不需要（遍历是核心，无效路径也需走完） | 必须（剪枝是核心优化，提前跳过无效路径） |
二、什么时候用回溯法？（4 类典型场景）
回溯法的核心是「试错 + 回退」，适用于需要枚举所有可能方案，并筛选出符合条件解的问题，且这类问题通常需要「维护临时路径 / 状态」，并在试错后撤销选择。
场景 1：组合 / 子集 / 排列类问题
- 特征：从一组元素中选若干个，满足「长度 / 和 / 去重」等条件，需返回所有符合条件的组合 / 排列 / 子集。
- 典型例子：
- LeetCode 77：1~n 中选 k 个数的所有组合；
- LeetCode 46：数组的全排列；
- LeetCode 39：组合总和（选数和为 target）；
- LeetCode 78：数组的所有子集。
- 为什么用回溯：需要尝试「选某个数→递归→不选这个数（撤销）→选下一个数」，并筛选出满足条件的组合，必须显式回退状态。
场景 2：分割类问题
- 特征：将一个字符串 / 数组分割成若干部分，每部分满足特定条件，需返回所有合法分割方案。
- 典型例子：
- LeetCode 131：分割回文串（分割后每个子串都是回文）；
- LeetCode 93：复原 IP 地址（分割成合法的 4 段 IP）。
- 为什么用回溯：需要尝试「在某个位置分割→递归验证后续→撤销分割→尝试下一个位置」，需维护当前分割的路径。
场景 3：棋盘 / 布局类问题
- 特征：在固定布局中放置元素，满足「不冲突」条件，需返回所有 / 任一合法布局。
- 典型例子：
- LeetCode 51：N 皇后（皇后不互相攻击的所有布局）；
- LeetCode 37：数独求解（填充数独的合法方案）。
- 为什么用回溯：需要尝试「在某个位置放元素→验证冲突→递归→撤销放置→试下一个元素」，必须回退状态才能试错。
场景 4：选数 / 决策类问题
- 特征：通过多步决策选择元素，满足全局条件，需返回所有合法决策路径。
- 典型例子：
- 目标和问题（从数组选数，和为 target 的所有选法）；
- 括号生成（LeetCode 22：生成所有有效的 n 对括号）。
- 为什么用回溯：每一步决策（如加左括号 / 右括号）会影响后续，需「选→递归→撤销→选另一选项」。
三、什么时候用普通 DFS？（4 类典型场景）
普通 DFS 的核心是「遍历 / 验证」，适用于只需确认 “是否存在”“有多少个”“遍历所有节点”的问题，无需维护持久化的路径状态，递归栈自然回溯即可。
场景 1：树 / 图的遍历与计数
- 特征：遍历所有节点 / 边，统计数量、打印路径或验证结构。
- 典型例子：
- 二叉树的前 / 中 / 后序遍历；
- 统计二叉树的节点数、叶子节点数；
- 图的所有节点遍历（无向图 / 有向图）。
- 为什么用普通 DFS：只需按顺序遍历，无需撤销状态，递归返回后自然回到父节点 / 上一节点。
场景 2：连通性验证与区域统计
- 特征：判断节点是否连通，或统计连通区域的数量 / 大小。
- 典型例子：
- LeetCode 200：岛屿数量（统计二维网格中连通的陆地数量）；
- 判断图中是否存在从起点到终点的路径；
- 统计图的连通分量个数。
- 为什么用普通 DFS：只需标记已访问节点，遍历所有连通节点即可，无需回退标记（标记是为了避免重复遍历，而非 “撤销选择”）。
场景 3：路径存在性验证
- 特征：验证是否存在满足简单条件的路径，无需返回所有路径。
- 典型例子：
- 二叉树中是否存在和为 target 的路径；
- 图中是否存在环；
- 矩阵中是否存在从左上角到右下角的路径（仅需判断存在性）。
- 为什么用普通 DFS：找到一条有效路径即可返回，无需枚举所有路径，无需维护完整路径状态。
场景 4：简单的递归搜索（无状态冲突）
- 特征：递归过程中无共享状态，无需恢复状态。
- 典型例子：
- 求二叉树的最大深度；
- 验证二叉树是否为平衡二叉树；
- 找二叉树的最近公共祖先。
- 为什么用普通 DFS：递归仅计算子问题结果，无 “选择 - 撤销” 的试错过程，状态随递归栈自然销毁。
四、易混淆场景的区分（关键案例）
| 问题 | 用 DFS 还是回溯？ | 核心原因 |
|---|---|---|
| 岛屿数量（LeetCode 200） | DFS | 目标是统计连通区域，仅标记已访问节点，无 “选择 - 撤销” 的试错过程 |
| N 皇后（LeetCode 51） | 回溯法 | 需尝试放置皇后，冲突则撤销（回退），并枚举所有合法布局 |
| 二叉树路径总和（仅判断存在） | DFS | 只需验证是否存在路径，无需保存所有路径，递归找到即返回 |
| 二叉树路径总和（返回所有路径） | 回溯法 | 需维护当前路径，递归后撤销最后一个节点，才能枚举所有符合条件的路径 |
| 数独求解 | 回溯法 | 需尝试填充数字，无效则回退，属于 “试错 - 撤销” 的解空间搜索 |
五、总结：快速选择方法
- 若问题需要枚举所有符合条件的解（组合 / 排列 / 分割 / 布局）→ 用回溯法；
- 若问题只需遍历 / 验证 / 计数（连通性 / 路径存在 / 节点数）→ 用普通 DFS；
- 核心差异：是否需要「显式维护路径 / 选择状态，并在递归后撤销」—— 需要则回溯，不需要则 DFS。
结合代码特征更易判断：
- 回溯法代码必有「选择（path 添加元素）→ 递归 → 撤销（path 移除元素）」的逻辑；
- 普通 DFS 代码只有「递归遍历下一个节点」，无显式的撤销操作。