企业官网建设流程全解析

刷题群今天又有新人问：“P2118 排列字母，我直接用递归交换法，为什么输出要么多要么少？”这个话题基本每个月都会出现。排列字母这类题目，表面上看就是把给定字符串里的所有字符任意重排，输出全部不同结果。可一旦字符里有重复字母、还要求按字典序输出、字符串长度来到 8 或 10 的时候，“把所有排列列出来”这句话背后藏的全是细节：递归怎么写，重复怎么跳，顺序怎么保证，数据量大时又该怎么控制。我拿这道题当回溯入门题给新人讲了不知道多少次，今天干脆把我自己的完整解法、踩过的坑，以及从这道题延伸到组合问题的思路，全部整理出来，希望对正在刷 DFS 回溯算法题的你有帮助。

1. 表面是“全排列”，实际考的是“多重集排列”

1.1 题面到底在说什么

“排列字母”这类题目的常见描述是：给定一个由字符组成的字符串，把里面的所有字母任意重排，输出能够得到的所有不同字符串，并且要求按字典序从小到大输出。听起来似乎不需要任何算法，全排列嘛，三层循环的事情——那只是“abc”这种三个字母不重复的情况。真实场景里字符串可能长这样：aab、abca、aabbcc，同一个字母出现一次以上，朴素的全排列代码跑出来会有大量重复结果，一提交就是 WA。

这里有一个重要的数学背景：没有重复元素的排列，数量是 n!；一旦某个元素重复了 t 次，最终排列数按 n! / t! 计算，多个元素重复则连除多个 t!。这种“带重复元素”的排列在离散数学里叫多重集排列。题目起名“排列字母”，考的就是这个东西。

我第一次见到这道题时，也是先写了递归交换法，然后把输出结果塞进 set 去重。小数据跑得挺欢，长度一到 9、10，风扇就开始狂转，内存也快爆了。所以，“把答案都塞进 set 再输出”能不能过，只看数据有多水，但这不是算法竞赛想让你掌握的解法。这道题真正想考的，是一个足够干净、足够省内存、能直接按字典序生成结果的 DFS 回溯方案。

1.2 为什么一道入门题卡住这么多人

P2118 这类题刷的人多，但讨论区里永远有一堆相似问题：“为什么我输出多了？”“为什么少了 ab 开头的结果？”“明明测试用例对，一提交就 TLE？”原因在于，这种题不考多深的算法，但把 DFS 回溯里的三个基本功全考了一遍：状态定义是否清晰、递归返回时状态能否正确还原、重复元素如何处理。任何一个环节想不清，代码都会在某些边界数据上翻车。

更麻烦的一点是输出顺序和字典序挂钩。如果不做任何处理，DFS 的遍历顺序很可能不是字典序。解决办法不是到最后统一排序，而是从一开始就让搜索顺序和字典序保持一致——先把字符串排个序，然后在每一层按顺序选择候选字符。这一点后面会展开。

2. 先写无重复版本：DFS 回溯到底在做什么

2.1 递归状态模型

先看最干净的情况：输入字符串 “abc”，所有字符都不同，目标是输出 6 个排列。搜索过程可以看成递归状态树：

• 第一层决定第一个位置放谁，候选是 a、b、c；
• 选中 a 后进入第二层，候选剩下 b、c；
• 选中 b 后进入第三层，只剩 c，于是得到 abc；
• 回到第二层的“b 已经用过”状态，改选 c，得到 acb；
• 再回到第一层，把 a 收回去，改选 b，继续在第二层尝试 a、c……

最终得到全部 6 个排列：abc、acb、bac、bca、cab、cba。

这个“回到上一层、换一个候选”的动作，就是回溯。代码上对应两句话：递归调用前把当前字符标记为已用，递归调用后立刻取消标记。取消标记这一句极其关键，它保证同一条递归路径的兄弟分支之间互不影响。如果你把取消标记忘了，第一次递归结束后所有字符都变成已用，后面的分支什么都选不出来，输出会少一大半，而且每一条输出看起来都正常，很迷惑人。

2.2 标准模板与三个容易忽略的细节

无重复版本的 C++ 模板如下：

#include <bits/stdc++.h> using namespace std; string s; bool used[15]; vector<string> ans; void dfs(string cur) { if ((int)cur.size() == (int)s.size()) { ans.push_back(cur); return; } for (int i = 0; i < (int)s.size(); i++) { if (used[i]) continue; used[i] = true; dfs(cur + s[i]); used[i] = false; } } int main() { cin >> s; sort(s.begin(), s.end()); dfs(""); for (auto &str : ans) cout << str << "\n"; return 0; }

写这个模板时有三个细节我会反复提醒。

第一，used 数组的长度要和原字符串长度一致，而不是和字母种类数一致。即使两个位置的字符值相同，它们在数组里也是不同的下标，used 区分的是“位置”，不是“字符值”。这正是后面去重剪枝能工作的基础。

第二，遍历候选时从 0 扫到 n-1，而不是维护一个“剩余字符集合”。这样写的好处是：配合排序后的字符串，DFS 的自然遍历顺序就能按字典序生成排列。如果维护剩余集合，还得额外保证每次取出最小字符，代码复杂不少。

第三，终止条件用 cur.size() == s.size()，不是 cur.size() == n - 1。见过有人写错，导致最后一个字符永远进不来，输出全是长度少一位的残缺排列。这类错误在本地小样例里很难发现，因为长度短的排列看起来也像“某种合理结果”。

3. 关键的一行剪枝：相同字符只取第一个放进来

3.1 重复从哪来

现在进入真正的主题：输入 aab，目标输出只有 3 行，但朴素 DFS 会给出 6 行。问题出在 used 数组把两个 a 当成两个独立候选：先取下标 0 的 a 再取下标 1 的 a，和先取下标 1 的 a 再取下标 0 的 a，两条不同的搜索路径生成了完全相同的字符串 “aab”。同理，所有含重复字符的排列都会成倍出现。

去重的目标就是让两个 a 不再被当成两个选择。更准确地说，让所有值相同的字符保持一个固定的先后顺序，递归时只能按这个顺序依次取，这样就不会生成同一种排列的多个副本。

3.2 正确剪枝与常见错误写法

在标记数组法中，去重的标准写法是在 for 循环里加一行：

if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue;

翻译成人话：当前这个字符和前一个字符值相同，但前一个同样值的字符还没被用过，说明我不该越过它先取后面的同值字符，所以跳过这次选择。

这个条件成立有两个前提。一个是递归前已经把字符串按字符值排序，让相同字符都挨在一起；另一个是 for 循环从 0 开始升序扫描。只有当前一个同值字符已经处于 used 状态时，才允许继续取 s[i]，这样重复字符永远按从左到右的顺序被使用。

很多人喜欢把条件改成used[i - 1]，意图是“前一个用过了所以跳过后面的重复项”，但这是错的。改成 used[i-1] 之后，当你先取了后面的 a、再想取前面的 a 时，就会被允许，依然产生重复；而当你应该连续取两个 a 的合法路径中，第二个 a 在第一个 a 已用的情况下反而被跳过，造成漏解。这个错误极其隐蔽，因为输出的每一行看起来都是合法排列，只是行数不对。判断方法很简单：用 aab 验证，如果输出不是 3 行，先检查这一行条件写反没有。

还有一个等价写法值得了解：在递归函数内部用 bool 数组记录某一层已经选过哪个字符值，遇到 used 检查通过但 seen[当前字符] 为 true 就跳过。这个方法不要求字符串预排序，但要额外开一个数组，代码不如排序法简洁。我更推荐排序加相邻判定的写法，思路更接近“把重复项合并到一个候选”的本质。

3.3 用一个例子验证

用 aab 验证：sort 后还是 aab。DFS 第一层从下标 0 开始，先取下标 0 的 a，后续可以取下标 1 的 a 或 b，得到 aab、aba；接着循环到下标 1，发现 s[1] == s[0] 且下标 0 未被使用，直接 continue，不会生成以第二个 a 开头的重复分支；最后取 b，得到 baa。最终 3 行：aab、aba、baa，而且天然是字典序。

如果把剪枝条件写反成used[i - 1]，结果会怎样？以 aab 为例，第一层取下标 1 的 a 时，因为下标 0 的 a 未被使用，used[0] 为 false，条件不成立，于是可以取，生成以“第二个 a”开头的重复路径。更糟糕的是，当第一层取下标 0 的 a 后，第二层想取下标 1 的 a 时，used[0] 已经为 true，条件变成 true，会跳过这个 a，导致 aab 这个合法排列直接少掉。试一下就明白，这种错误比输出重复更难受。

4. 交换法也能做，但字典序会被打乱

4.1 交换法思路与去重实现

除了标记数组法，还有一种同样经典的写法：交换法。它不用 used 数组，递归时直接把当前位置和后边某个位置交换，递归返回后再换回去。核心代码如下：

#include <bits/stdc++.h> using namespace std; string s; vector<string> ans; void dfs(int idx) { if (idx == (int)s.size()) { ans.push_back(s); return; } for (int i = idx; i < (int)s.size(); i++) { bool dup = false; for (int j = idx; j < i; j++) { if (s[j] == s[i]) { dup = true; break; } } if (dup) continue; swap(s[idx], s[i]); dfs(idx + 1); swap(s[idx], s[i]); } } int main() { cin >> s; sort(s.begin(), s.end()); dfs(0); for (auto &str : ans) cout << str << "\n"; return 0; }

这段代码的精髓在于：s 本身既是输入，也是搜索过程中被不断改写的临时数组。dfs(idx) 执行时，0 到 idx-1 位置已经定好，只需决定 idx 位置放哪个字符。把 s[idx] 和后面某个 s[i] 交换，就是在尝试一种放法；递归返回后再交换回来，保证下一次尝试面对的还是最初顺序。

交换法的去重逻辑也不一样：对于当前 idx 位置，只要某一个字符值已经作为 s[i] 被尝试过，后续同样的字符值就不再尝试。内层 for 循环检查从 idx 到 i-1 之间有没有和 s[i] 相同的字符，有就跳过。这个写法和标记数组法的去重本质相同，都是让重复字符的相对顺序固定下来。

4.2 两种方法的取舍

交换法有明显优点：空间 O(n)，不需要额外的 used 数组，代码在组合类题目里也经常能顺手改造。但它有一个让我最开始很不爽的缺点：生成结果的顺序不是字典序。

原因很简单。第一次进入 dfs(0) 时，for 循环从 i=0 开始，先交换自身，生成以此开头的分支；但 i=1 时把 s[0] 和 s[1] 交换，会立刻生成以另一个字符开头的分支，这个分支可能在字典序更小的一些排列之前出现。递归层越来越深，顺序越来越乱。

如果题目严格要求字典序，有两种补救路径：

• 把所有排列存进 vector，等 dfs 结束后统一 sort。n≤8 时完全可行，n=10 时排列数约 362 万，排序一次也还能接受；
• 在每次交换返回后对 s 的子串重新排序，强制恢复字典序，但代码复杂度明显上升，很多初学者在这里写错。

标记数组法则没有这个烦恼：只要输入字符串先 sort，递归天然按字典序生成结果。我个人的建议是，这道题优先掌握标记数组法，交换法作为扩展理解。以后做组合类题目、n 皇后、图的全排列时，再回头把交换法捡起来也不迟。

下面这个对比是我给新人总结的，比较直观：

5. 先算算排列数量，再决定要不要枚举

5.1 多重集计数公式与极限

做“排列字母”这类题，动手写递归之前先做一道算术题：确认输出规模在可枚举范围内。

如果输入字符串长度为 n，每个字符的出现次数记为 cnt[c]，那么实际不同排列数是：

res = n! / (cnt[0]! * cnt[1]! * ... * cnt[25]!)

举个例子：abca 的长度是 4，a 出现 2 次，其余各 1 次，所以结果是 4! / 2! = 12。aabbcc 的长度是 6，三种字母各出现 2 次，结果是 6! / (2! * 2! * 2!) = 90。这个公式一方面用来估算程序运行时间，另一方面可以用来验证输出行数——跑完数一下 ans.size() 对不对，对拍时特别好用。

阶乘膨胀有多快？下面列几个常见值感受一下：

• n=8：40320
• n=10：3628800
• n=12：479001600
• n=15：1307674368000

如果题目给的字符串长度到了 15 还要求输出所有排列，哪怕每个排列只算一遍，输出量也是千亿级别，任何程序都不可能跑完。所以这类题目的长度一般会控制在 8 到 10 左右，最多到 12 但会加很多重复字符。看到长度超过这个范围，就应该立刻怀疑题目要的其实是“输出第 k 个排列”或“只求排列数量”，而不是全量枚举。这是比写递归更优先的判断。

5.2 输出量和IO层面的工程细节

枚举全排列还有一个常被忽略的瓶颈：输出本身。n=10 全不同时排列数约 362 万，每个排列一行，就是 362 万行。如果每行长度又接近 10，总输出量超过 30MB。对 OJ 来说这不算超大，但如果你用 cout 的默认同步模式，整块的缓冲区刷新可能拖慢好几倍。

我的习惯是做题前先加两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

它们能大幅减少 C++ 标准流和 C 标准库之间的同步开销。输出用 '\n' 而不是 endl，因为 endl 会强制刷新缓冲区，在这种大批量输出的场景里是明显的性能杀手。

另一个工程细节在 dfs 的参数上。模板里用dfs(cur + s[i])，每递归一层就构造一个新字符串，n=10 时会产生大量的临时 string 对象，虽然不难扛，但压力不小。想进一步优化，可以改用 char 数组和长度变量：

#include <bits/stdc++.h> using namespace std; string s; bool used[15]; vector<string> ans; char buf[20]; void dfs(int len) { if (len == (int)s.size()) { buf[len] = 0; ans.push_back(buf); return; } for (int i = 0; i < (int)s.size(); i++) { if (used[i]) continue; if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue; used[i] = true; buf[len] = s[i]; dfs(len + 1); used[i] = false; } } int main() { cin >> s; sort(s.begin(), s.end()); dfs(0); for (auto &str : ans) cout << str << "\n"; return 0; }

这段写法在大型枚举题里更稳。buf 是全局变量，同一时刻只有一个递归分支在写它，所以大家共享一块内存也没问题，遇到终止条件时把当前长度位置截断成一个字符串存入 ans。

6. 从WA到AC：我的复现测试清单

6.1 固定回归用例

我复盘自己从 WA 到 AC 的经验，发现固定测试集比随机造数据高效得多。下面这组用例每次写完新解法都会跑一遍：

每一个用例都有对应的验证目标：长度为 1 测试边界；全同字符测试极端去重；aab 测试“有重复但不多”的情况；abc 测试无重复基准；abca 测试重复和非重复字符混合的情况。跑完这几个还 WA，大概率不是算法思路问题，而是输入输出细节。

6.2 五个高频翻车点

第一，used 标记忘记恢复。表现为程序只输出很少几行甚至只有一行，因为第一层递归结束后所有 used 都为 true，后面的 for 循环一个候选都选不出来。检查方法很简单：在递归调用后立刻看有没有 used[i] = false。

第二，去重条件写反。!used[i - 1]和used[i - 1]的区别，我是用 aab 这个用例才彻底看清的。用反之后 aab 会少输出 aba 或 baa，并且每一行看起来都合法，所以非常难排查。如果你发现答案数量和数学公式对不上，先怀疑这里。

第三，忘了 sort 输入。标记数组法的字典序依赖排序后的字符串顺序。如果不排序，答案可能是对的，但顺序是乱的。有些题目数据弱，靠最后统一 sort 也能救回来，但不如在一开始就 sort 干净。

第四，输出格式问题。多一个末尾空格通常无所谓，但少一个换行很容易判 PE。每个排列之间要换行，不要用空格隔开，更不要用逗号。

第五，多组测试数据时没有清空全局状态。如果题目输入包含多组字符串，每跑完一组要清空 used 数组和 ans 向量，否则第一组 AC 后，第二组的输出里会混进旧结果。这个坑在本地单数据样例上根本测不出来，只有提交后会暴露。

最后再分享一个小技巧：排列字母这类题我一般会让新人连写三遍——先用标记数组法 AC 一遍，再用交换法写第二遍，第三遍再用 next_permutation 水一遍。三遍下来，DFS 回溯的“选择、搜索、撤销”三个动作、重复元素剪枝、字典序与递归路径顺序的关系基本都吃透了。之后遇到“从 N 个字符里选 M 个”的组合题，把终止条件从“当前路径长度等于 n”改成“等于 m”，再在循环起点上稍微限制，就能无缝迁移过去。这也是我拿 P2118 反复讲的原因——它不是难，而是正好卡在“刚会模板但还不懂细节”的位置上。