带路径信息的 DFS 必须显式维护路径容器，因递归栈只存执行上下文而非业务路径；漏 push 或 pop 会导致路径错乱或内存爆炸，常见于迷宫路径记录、树中目标和路径枚举等场景。
直接说结论：带路径信息的 DFS 必须显式维护路径容器（如 vector 或 stack），且每次递归进入前 push，回溯前 pop —— 漏掉任一端，路径就错乱或内存爆炸。
为什么不能只靠递归调用栈记路径？
递归调用栈只保存“执行上下文”，不保存你关心的业务路径（比如经过的节点编号、边权序列、字符串拼接结果）。一旦需要输出完整路径、比较多条路径长度、或在终止条件里校验路径性质（如是否回文、总和是否达标），就必须自己管。
常见错误现象：vector<int> path</int> 传值传递导致每层都是副本，回溯失效；或传引用但忘了 pop_back()，后续分支路径越积越多。
使用场景举例：迷宫中记录从起点到终点的坐标序列、树中找和为 target 的所有路径、图中枚举所有简单路径（无重复点）。
立即学习“C++免费学习笔记（深入）”；
- 参数差异：推荐用
vector<int>& path</int>引用传入，避免拷贝开销 - 性能影响：频繁
push_back/pop_back是 O(1) 均摊，但若路径很长（如万级节点），要考虑是否真需全程存——可改用 parent 数组 + 终止时反向重构
dfs() 函数里怎么安全更新和还原路径？
核心动作只有两步：进入子节点前把当前节点加进路径，离开前把它拿掉。中间任何提前 return（如越界、访问过、剪枝失败）都必须保证 pop_back() 被执行，否则路径状态污染后续分支。
实操建议用「作用域守卫」式写法，避免遗漏：
void dfs(int x, int y, vector<pair<int,int>>& path) {
path.push_back({x, y});
if (x == endX && y == endY) {
allPaths.push_back(path); // 保存一份拷贝
path.pop_back(); // 别忘还原！
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (!valid(nx, ny) || visited[nx][ny]) continue;
visited[nx][ny] = true;
dfs(nx, ny, path);
visited[nx][ny] = false;
}
path.pop_back(); // 所有分支结束，当前层退出，弹出自己
}
容易踩的坑：allPaths.push_back(path) 必须是拷贝（path 是引用）；pop_back() 写在递归调用后但没覆盖所有出口（比如漏了剪枝 return）；visited 状态没同步还原。
非递归 DFS 怎么带路径？用 stack 存什么？
不能只压坐标，得压“当前节点 + 到达它的完整路径”或“当前节点 + 父节点索引”。前者直观但内存高；后者省空间，但需额外结构存路径映射。
推荐组合压入：stack<tuple<int, int, vector<int>>>（坐标 + 当前路径），但注意 vector 拷贝成本；更高效的是压入 struct { int x, y; int pathLen; }，再配一个全局 vector<int> fullPath，用 pathLen 截取前缀。
性能影响：非递归避免栈溢出，但显式管理路径逻辑变重；若路径只需最终结果（如最短/最长），可改用 BFS 更自然。
兼容性提醒：stack 默认适配器是 deque，若大量 push/pop 且对缓存敏感，可换 vector 作为底层容器。
路径去重和剪枝的关键检查点
带路径的 DFS 最容易在“是否允许重复访问节点”上出错。网格迷宫通常不允许（visited 全局标记）；而某些图问题允许（如带权图找所有路径，节点可重复但边不可）。
必须在两个地方检查：
- 进入
dfs()第一行：判断当前节点是否已在path中（O(n)查找，路径长时考虑哈希集合缓存） - 方向循环内：判断下一步是否越界、是否墙、是否已访问（按题意决定是查
visited还是查path）
容易被忽略的地方：路径长度限制（如最多走 10 步）、路径内容约束（如相邻节点值差不能超 2）必须在递归入口或方向尝试前检查，否则无效分支照常展开，浪费严重。
