刷题群今天又有新人问“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]; vectorstring 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; vectorstring 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 循环从 i0 开始先交换自身生成以此开头的分支但 i1 时把 s[0] 和 s[1] 交换会立刻生成以另一个字符开头的分支这个分支可能在字典序更小的一些排列之前出现。递归层越来越深顺序越来越乱。如果题目严格要求字典序有两种补救路径把所有排列存进 vector等 dfs 结束后统一 sort。n≤8 时完全可行n10 时排列数约 362 万排序一次也还能接受在每次交换返回后对 s 的子串重新排序强制恢复字典序但代码复杂度明显上升很多初学者在这里写错。标记数组法则没有这个烦恼只要输入字符串先 sort递归天然按字典序生成结果。我个人的建议是这道题优先掌握标记数组法交换法作为扩展理解。以后做组合类题目、n 皇后、图的全排列时再回头把交换法捡起来也不迟。下面这个对比是我给新人总结的比较直观对比项标记数组法交换法额外空间需要 used 数组不需要原地交换字典序输入排序后天然有序通常需要额外排序或补救去重实现相邻字符加 used 判断内层循环查重复理解难度符合“选择-搜索-撤销”直觉需要适应交换和还原适用场景全排列、组合、DFS 回溯排列构造、剪枝类题目5. 先算算排列数量再决定要不要枚举5.1 多重集计数公式与极限做“排列字母”这类题动手写递归之前先做一道算术题确认输出规模在可枚举范围内。如果输入字符串长度为 n每个字符的出现次数记为 cnt[c]那么实际不同排列数是res n! / (cnt[0]! * cnt[1]! * ... * cnt[25]!)举个例子abca 的长度是 4a 出现 2 次其余各 1 次所以结果是 4! / 2! 12。aabbcc 的长度是 6三种字母各出现 2 次结果是 6! / (2! * 2! * 2!) 90。这个公式一方面用来估算程序运行时间另一方面可以用来验证输出行数——跑完数一下 ans.size() 对不对对拍时特别好用。阶乘膨胀有多快下面列几个常见值感受一下n840320n103628800n12479001600n151307674368000如果题目给的字符串长度到了 15 还要求输出所有排列哪怕每个排列只算一遍输出量也是千亿级别任何程序都不可能跑完。所以这类题目的长度一般会控制在 8 到 10 左右最多到 12 但会加很多重复字符。看到长度超过这个范围就应该立刻怀疑题目要的其实是“输出第 k 个排列”或“只求排列数量”而不是全量枚举。这是比写递归更优先的判断。5.2 输出量和IO层面的工程细节枚举全排列还有一个常被忽略的瓶颈输出本身。n10 全不同时排列数约 362 万每个排列一行就是 362 万行。如果每行长度又接近 10总输出量超过 30MB。对 OJ 来说这不算超大但如果你用 cout 的默认同步模式整块的缓冲区刷新可能拖慢好几倍。我的习惯是做题前先加两行ios::sync_with_stdio(false); cin.tie(nullptr);它们能大幅减少 C 标准流和 C 标准库之间的同步开销。输出用 \n 而不是 endl因为 endl 会强制刷新缓冲区在这种大批量输出的场景里是明显的性能杀手。另一个工程细节在 dfs 的参数上。模板里用dfs(cur s[i])每递归一层就构造一个新字符串n10 时会产生大量的临时 string 对象虽然不难扛但压力不小。想进一步优化可以改用 char 数组和长度变量#include bits/stdc.h using namespace std; string s; bool used[15]; vectorstring 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 的经验发现固定测试集比随机造数据高效得多。下面这组用例每次写完新解法都会跑一遍输入期望输出说明a恰好一行 aaa恰好一行 aaaab三行aab、aba、baaabc六行abc、acb、bac、bca、cab、cbaabca12 行且没有重复行严格字典序每一个用例都有对应的验证目标长度为 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 反复讲的原因——它不是难而是正好卡在“刚会模板但还不懂细节”的位置上。