回溯

Tip

b站讲解
 CSDN

1. 回溯算法（Backtracking）

回溯算法是一种 通过尝试所有可能选择，并在发现当前路径不行时返回重新选择 的搜索方法。

核心思想：

走得通就继续走，走不通就退回来换条路。

这就像走迷宫：

选一条路前进
发现死路
返回上一个路口
改走别的路

这就是回溯。

2. 回溯的本质

回溯 = 深度优先搜索（DFS） + 撤销操作

流程通常是：

做选择
进入下一层递归
返回时撤销选择

所以它特别适合：

全排列
组合问题
子集问题
N 皇后
数独
迷宫路径

3. 回溯模板

void dfs(参数)
{
    if(到达终点状态)
    {
        输出答案;
        return;
    }

    for(所有可选方案)
    {
        if(当前选择合法)
        {
            做选择;
            dfs(下一状态);
            撤销选择;
        }
    }
}

记住这三步：

选
递归
撤销

4. 为什么要撤销

因为递归返回后，要尝试其他分支。

例如排列数字：

1 2 3
1 3 2

当你选完：

1 2

返回后，必须把 2 取消掉，才能改选 3。

所以撤销操作非常关键。

5. 经典例子：输出 1~3 的全排列

#include <iostream>
using namespace std;

int path[10];
bool used[10];
int n = 3;

void dfs(int step)
{
    if(step > n)
    {
        for(int i = 1; i <= n; i++)
            cout << path[i] << " ";
        cout << endl;
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!used[i])
        {
            path[step] = i;
            used[i] = true;

            dfs(step + 1);

            used[i] = false;
        }
    }
}

int main()
{
    dfs(1);
}

输出：

6. 执行过程理解

先选 1

再选 2

1 2

再选 3

1 2 3

完成一组答案后返回：

撤销 3
改选别的数

这就是不断试错与返回。

7. 常见题型

全排列

从 n 个数中排顺序。

组合问题

选若干个数。

子集问题

每个数选或不选。

迷宫问题

找路径。

N 皇后

棋盘放皇后互不攻击。

8. 回溯和暴力搜索的关系

回溯本质也是暴力搜索，但更聪明。

普通暴力：

把所有情况直接列出来。

回溯：

一边构造答案，一边发现不行就提前返回。

因此效率更高。

9. 常见优化：剪枝

如果当前状态已经不可能成功，就直接停止。

例如：

选的数之和已经超过目标值

无需继续搜索。

这叫剪枝。

剪枝能大幅提高速度。

10. 常见错误

忘记撤销状态

例如：

used[i] = true;
dfs(...);
// 忘了 used[i] = false;

会导致后面无法继续搜索。

终止条件写错

递归层数不对，可能死循环或少答案。

数组越界

层数和下标混乱。

11. 如何判断题目用回溯

看到这些关键词时要警觉：

输出所有方案
求所有排列
求所有组合
找所有路径
n 很小（如 n ≤ 10）

通常就是回溯题。

12. 一句话理解

回溯算法 = 试一条路，不行就退回来换路继续试。

13. 总结

回溯算法的核心只有一句话：

做选择
递归搜索
撤销选择

掌握它之后，你就能解决大量搜索类题目。