回溯

一句话理解

回溯在搜索里：尝试一个选择，递归，再撤销。

为什么要学

排列、八皇后、走迷宫要恢复路径时。

讲解

改 → 递归 → 改回来。三条必须对齐。

连通块不回溯 vis；找路径、构造方案常常要回溯。

例子

八皇后：这一行放一列，递归下一行，返回后拿掉皇后。

常见错误

• 漏撤销某一维标记（列、对角线）。
• 连通块误回溯导致重复计数。