回溯算法：
第一课：魔法森林里的岔路口
今天我们不急着背代码，也不急着学习复杂的算法。
我们先讲一个有趣的故事：小兔子进入魔法森林，遇到了一个又一个岔路口。它需要学会选择道路、记录走过的路，并在走不通的时候返回，尝试新的道路。
当你学会了这套方法，就掌握了回溯算法最重要的思想。
一、故事开始：小兔子的魔法探险
一天，小兔子收到了一张藏宝图。
藏宝图告诉它：
从起点出发。
每个岔路口只能选择左边或右边。
走到终点，就完成一次探险。
如果走到死路，就返回上一个岔路口，换一条路。
小兔子来到第一个岔路口。
小兔子先走左边，再继续探索。走到底后，它还要返回岔路口。
我们来想一想：
如果小兔子只知道向前走，却不知道如何返回，那么它可能永远无法探索其他道路。
所以，它必须学会三个动作：
选择 → 探索 → 撤销选择
这就是回溯算法的核心思想。
二、认识回溯：三个重要动作
1. 选择：我决定走哪条路
例如，小兔子站在岔路口，可以选择左边，也可以选择右边。
在 C++ 中，我们可以用一个变量记录当前的选择：
choice = 0; // 选择左边
choice = 1; // 选择右边
2. 探索：沿着选择继续前进
选择左边之后，小兔子继续探索左边的道路。
如果前面还有岔路口，就继续做选择。
3. 撤销选择：返回岔路口
如果左边的道路已经探索完了，小兔子就返回岔路口，尝试右边。
这一步非常重要。
因为回溯算法不仅要记录当前的选择，还要知道什么时候恢复到之前的状态。
三、用一个简单问题学习回溯
假设小兔子连续遇到三个岔路口。
每个岔路口都只有两个选择：
选左边，记作
0。选右边，记作
1。
那么，三次选择可以组成什么样的路线呢？
例如：
000
001
010
011
100
101
110
111
一共有 8 种路线。
为什么？
因为每次选择都有两种可能，连续选择三次：
我们可以画出这棵搜索树：
每一层代表一次选择，最底层就是所有可能的路线。
我们发现：
-
第一层：第一次选择，有 2 种可能。
-
第二层：第二次选择，有 4 种可能。
-
第三层：第三次选择，有 8 种可能。
回溯算法就是按照这样的方式，把所有可能的路线一条一条探索出来。
四、把故事变成 C++ 程序
现在我们来编写一个程序，输出所有由 0 和 1 组成的三位数字。
第一步：准备记录路线的数组
int ans[3];
ans[] 就像小兔子的探险记录本。
-
ans[0]记录第一次选择。 -
ans[1]记录第二次选择。 -
ans[2]记录第三次选择。
第二步：编写回溯函数
void dfs(int x) {
if (x == 3) {
cout << ans[0] << ans[1] << ans[2] << endl;
return;
}
ans[x] = 0;
dfs(x + 1);
ans[x] = 1;
dfs(x + 1);
}
第三步：完整程序
#include <iostream>
using namespace std;
int ans[3];
void dfs(int x) {
if (x == 3) {
cout << ans[0] << ans[1] << ans[2] << endl;
return;
}
// 选择左边
ans[x] = 0;
dfs(x + 1);
// 选择右边
ans[x] = 1;
dfs(x + 1);
}
int main() {
dfs(0);
return 0;
}
五、逐步理解程序
我们用 dfs(x) 表示：
现在要决定第
x次选择。
当 x == 3 时，说明三次选择都已经完成，可以输出一条完整路线。
例如：
dfs(0)
ans[0] = 0
dfs(1)
ans[1] = 0
dfs(2)
ans[2] = 0
dfs(3) → 输出 000
ans[2] = 1
dfs(3) → 输出 001
接下来，程序会返回上一层，继续尝试其他选择。
注意：这里的“返回”不是把程序重新启动，而是让函数执行完毕后，回到调用它的位置，继续执行后面的代码。
六、为什么回溯需要撤销选择？
假设小兔子已经走到了：
0 → 0 → 0
现在它要尝试：
0 → 0 → 1
它只需要把最后一次选择从 0 改成 1。
这就是撤销选择。
在本课中，ans[x] = 1 会覆盖原来的 0，因此不需要额外写一行恢复代码。
但在后续的排列、组合和迷宫问题中，我们经常需要这样写：
used[i] = true;
dfs(x + 1);
used[i] = false;
这就是回溯算法中非常经典的“恢复现场”。
七、课堂练习
练习 1：两次选择
小兔子只需要做两次选择，每次可以选 0 或 1。
请你写出所有可能的路线。
练习 2：四次选择
如果小兔子需要做四次选择，一共有多少种路线？
请尝试修改程序，让它输出所有四位路线。
练习 3：加入限制
如果小兔子连续两次不能都选择 1，那么有哪些路线是合法的？
试着在程序中加入判断条件，只输出符合要求的路线。
本课记忆口诀：
选择一条路，记录当前选择；深入去探索，走完就返回；撤销旧选择，再试另一条路。
这就是回溯算法最基本的思维方式。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/weixin_60445850/article/details/170124873
