今天和大家分享一道经典的回溯题：串变换。然后我想把我对于这道题的一些好的想法和大家分享一下（已经很久没有这么好的想法了）。
算法竞赛里有一个哲学：“最好的数据结构就是没有数据结构，最好的状态管理就是原地可逆”。也就是很多大佬常说的：”能不用就不用，能原地就原地，能可逆就可逆”。
我其实最先开始也不太明白，但是在洛谷上看了大量大佬的题解后，大致明白了他们为何要这么说。
我想就这道题来和大家具体谈一谈。
具体题目如下：
我拆解了一下题目的大意：
给定两个长度为 n 的数字串S和T，以及 k 个操作。每个操作分了两种类型：
类型 1：1 x v：将 S[x] 变为 (S[x] + v) mod 10
类型 2：2 x y：交换 S[x] 和 S[y]
然后我们可以任选一些操作，以任意顺序执行，但每个操作至多用一次。问能否将 S 变成 T。
刚看到题可能会往贪心或者图论方向想，但我们注意到了k ≤ 7，这基本就是在明示搜索了。
那怎么搜索呢？官方是这么讲的：
确实经典,也确实巧妙。首先，确定了应该使用全搜索，因为这道题的核心在于操作的顺序敏感性。先执行操作A再执行操作B，与先B后A的结果可能完全不同。因此，我们需要尝试所有可能的操作执行顺序。（DFS 暴搜）
然后就开始套用经典的搜索模板：（通用模板）
记录路径：开一个vector<int> path，记录当前已经选了哪些操作的下标。
标记数组：开一个bool st[N]数组，用来标记第 i 个操作是否已经被加入路径，防止重复使用。
延迟验证：在 DFS 过程中不修改原串，而是等到递归到底（即确定了一个完整的操作序列）时，调用一个update()函数。在这个函数里，把原串 S 拷贝一份，然后按path里的顺序依次执行操作，最后看结果是否等于 T。
官方代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 25; // 操作数量上限（比题目给的 7 大一些，留有余量）
int n, k; // n: 字符串长度, k: 操作数量
string s, t; // s: 初始串, t: 目标串
int op[N], x[N], y[N]; // op[i]: 第 i 个操作的类型, x[i]/y[i]: 操作的参数
vector<int> path; // 当前选择的操作序列（按执行顺序存放操作编号）
bool st[N]; // st[i]: 第 i 个操作是否已经在 path 中
bool res; // 最终答案，true 表示可以变成 t
// 按照 path 中记录的操作顺序，依次执行所有操作，检查能否得到 t
void update()
{
string str = s; // 拷贝一份 s，在拷贝上模拟执行操作
for (int i = 0; i < path.size(); ++ i )
{
int j = path[i]; // j: 当前执行的操作编号
int a = op[j], b = x[j], c = y[j]; // a: 操作类型, b,c: 操作参数
if (a == 1)
// 类型 1：S[b] = (S[b] + c) mod 10
// -'0' 转数字，计算后再 +'0' 转回字符
str[b] = (str[b] - '0' + c) % 10 + '0';
else
// 类型 2：交换 S[b] 和 S[c]
swap(str[b], str[c]);
}
// 只要有一种排列能让 str == t，就标记为可行
res |= str == t;
}
// dfs(u): 当前正在构造 path 的第 u 个位置（从 1 开始编号）
void dfs(int u)
{
// 递归边界：已经选完 k 个位置（实际上 k 个操作不可能全用满，
// 但这里写 u == k + 1 是为了让所有小于等于 k 的排列都能走到 update）
if (u == k + 1)
{
update(); // 用当前排列模拟一次
return;
}
// 尝试在位置 u 放入一个尚未使用的操作
for (int i = 1; i <= k; ++ i )
if (!st[i]) // 操作 i 还没被用过
{
st[i] = true; // 标记为已使用
path.push_back(i); // 加入当前排列
dfs(u + 1); // 递归填下一个位置
path.pop_back(); // 回溯：撤出
st[i] = false; // 回溯：取消标记
}
// 关键：直接进入“不再选任何操作”的状态
// 这意味着允许 path 长度 < k，即只选部分操作
dfs(k + 1);
}
int main()
{
// 读入数据
cin >> n >> s >> t >> k;
for (int i = 1; i <= k; ++ i )
cin >> op[i] >> x[i] >> y[i];
dfs(1); // 从位置 1 开始构造排列
cout << (res ? "Yes" : "No") << endl;
return 0;
}
以上是官方给的代码，经典套模板，无懈可击，会回溯算法的也不难看懂。
但我今天偏偏就有一点第六感的存在，我当时就感觉不用开path数组，因为最后我们只需要输出yes或no，也就是我们不需要一个path数组来实时记录每一步的选择，从而来输出具体路径。还有就是本题操作足够简单：一个加法，一个交换，手动记录并恢复的成本极低，所以我感觉没必要用复杂的容器。
所以我产生了两个具体的疑问：
第一，开了一个 path 数组，把每一步选的什么操作都记下来，最后在 update() 里统一跑一遍。这相当于我走迷宫的时候，每走一步就掏本子记一笔，走到终点再翻本子从头走一遍——我都已经到终点了，干嘛还回去？
第二，st[i] 标记数组和 path 的手动
push/pop，每次都要小心翼翼配对，稍有不慎就漏恢复或者多恢复。这种"对称"操作的维护，纯靠人肉保证正确性。
于是我开始琢磨：能不能把这两个冗余干掉？
第一步：干掉 path——让字符串自己"动"起来：
大家仔细观察，会发现一个重要的事实：字符串的当前状态，就是路径的完整记录。
我走到某一层 DFS 的时候，字符串 S 已经被前面的操作改过了。那当前这一层的操作为什么不能直接作用在 S 上，而要留到update() 里在副本上重放呢？
问题在于：直接改 S 的话，递归返回之后怎么恢复？
这就引出了回溯的对称性原理：
类型 1（修改操作）：S[x] = (S[x] + v) % 10
我在执行前把原字符存下来：
char old = s[x[i]];
s[x[i]] = '0' + (old - '0' + y[i]) % 10; // 正向修改
dfs(...);
s[x[i]] = old; // 反向恢复
类型 2（交换操作）：swap(S[x], S[y])
这个更妙——swap 是自逆的。这是什么意思？你交换两个东西，想变回去，只需要再交换一次。不需要额外变量，不需要备份：
swap(s[x[i]], s[y[i]]); // 正向交换
dfs(...);
swap(s[x[i]], s[y[i]]); // 再交换一次 = 恢复
所以我压根不需要 path 了。 字符串 S 本身就是一个活的、时刻反映当前状态的东西。到任意一层，如果 S == T，直接返回true，不需要等到终点再统一判断。
所以我们砍掉了：
（1）vector<int> path 数组
（2）update() 整个函数
（3）每次到达终点的 O(n × k) 模拟开销
（4）res 变量——直接靠返回值就能判断
代码从两段式（"记录路径" + "统一回放"）变成了一段式（"边走边改，当场判断"）。
第二步：干掉 st 数组——用 bitmask 的"天然回溯"：
干掉 path 之后，还剩 bool st[10] 用来标记哪些操作已经用过了。它的问题是什么？
手动维护对称性。
每次选操作：
st[i] = true; // 标记
dfs(...);
st[i] = false; // 恢复 —— 这两行必须成对，缺一行就 bug
人不是编译器。忘了恢复、中间 return 了没恢复、多写了一个恢复——这些错误在实际编码中太常见了。
关键：k ≤ 7。
7 个操作，一个 int 有 32 位，绰绰有余。用二进制位的 1/0 表示操作是否被使用：
第 i 位 = 1 → 操作 i 已使用
第 i 位 = 0 → 操作 i 未使用
判断操作 i 是否用过：mask >> i & 1，一行。
但真正的杀手锏其实是传参。
bool dfs(int mask) {
...
dfs(mask | (1 << i)); // 把第 i 位置为 1，传给下一层
...
}
注意这里：mask | (1 << i) 是一个表达式，它不会改变当前层的 mask 变量本身。下一层递归收到的是一个新值，而当前层的 mask纹丝不动。
这意味着什么？递归返回后，mask 自动就是原来的值。你不需要写任何恢复语句。
这和 st[i] = true; dfs(...); st[i] = false; 形成了鲜明对比：
这叫天然回溯——语言的值传递机制帮我们保证了正确性，所以根本不用操心"恢复"这件事。
所以给出我的代码：
#include <bits/stdc++.h> // 万能头文件
using namespace std;
string s, t; // s: 初始串, t: 目标串
int k; // 操作数量
int op[7], x[7], y[7]; // 三个数组分别存每个操作：类型、参数1、参数2
/**
* dfs(mask): 搜索能否通过若干未使用的操作将 s 变成 t
* @param mask 二进制标记，第 i 位为 1 表示操作 i 已经被用过
* @return true 表示能从当前 s 状态到达 t
*/
bool dfs(int mask) {
// 剪枝：当前 s 已经等于 t，直接成功返回
if (s == t) return true;
// 枚举每一个操作，尝试作为"下一步"执行
for (int i = 0; i < k; i++) {
// 第 i 位已经用过则跳过
if (mask >> i & 1) continue;
if (op[i] == 1) {
// 类型 1：S[x[i]] = (S[x[i]] + y[i]) mod 10
char old = s[x[i]]; // 备份原字符
s[x[i]] = '0' + (old - '0' + y[i]) % 10; // 原地修改
if (dfs(mask | (1 << i))) return true; // 递归，传入新 mask
s[x[i]] = old; // 回溯恢复
} else {
// 类型 2：交换 S[x[i]] 和 S[y[i]]
swap(s[x[i]], s[y[i]]); // 原地交换
if (dfs(mask | (1 << i))) return true; // 递归，传入新 mask
swap(s[x[i]], s[y[i]]); // 回溯恢复（再 swap 一次即可）
}
}
// 所有路径都走不通，返回 false
return false;
}
int main() {
int n;
cin >> n >> s >> t >> k; // 读入长度、初始串、目标串、操作数
for (int i = 0; i < k; i++) { // 从 0 开始编号，方便位运算
cin >> op[i] >> x[i] >> y[i]; // 读入每个操作
}
// 从 mask = 0（没有任何操作被使用）开始搜索
cout << (dfs(0) ? "Yes" : "No");
return 0;
}
当然，这道题用官方解法固然也很巧妙，但我想说的是或许我们有时候深究一道算法题的时候才能发现一些新大陆。题固然得多刷，但培养算法思维与批判性思维或许更重要。就好比今天，在这道题上，我看出了：不需要一个path数组来实时记录每一步的选择，从而来输出具体路径，因为本题只要我们判断可行性，从而我自己尝试去删掉path数组来解题时，就已经是一种收获了。
如果还没学回溯算法的朋友们看到了这篇文章，建议先套用官方题解的模板（或者你自己去找模板），举一反三多刷几道回溯算法题（回溯其实很有意思），看看你是不是掌握了这个算法，然后再来思索一下我的这篇文章。
最后还是感谢一下能阅读到这篇文章的朋友们。
