回溯

一句话理解

回溯：走下去试试，不行就退回来改另一条路。

为什么要学

搜索题的核心动作。DFS 填格子几乎都是回溯。

讲解

三步：改状态 → 递归 → 撤销改动。撤销和改动必须配对。

和普通递归的差别是：会尝试多条分支，并且共享同一个状态数组。

例子

vis[x] = 1;
dfs(x);
vis[x] = 0; // 回溯

标记走过，搜索，再擦掉标记，允许别的路径再用这个点。若是图上找连通块，标记就不要擦。看题目要不要重复用。

常见错误

• 忘记撤销。
• 该保留标记时却回溯掉，连通块会算多次。