字符串排列全解析：回溯、去重与字典序的底层逻辑

如果你刷过一段时间剑指Offer大概会有一种感觉有些题是出题人拿来凑数的有些题则是面试官真正想让你留在黑板上的。字符串的排列属于后者。我第一次真正理解这道题不是在刷题平台上跑通的那天而是在后来一次模拟面试中对着白板讲了十分钟才发现自己其实根本没吃透。它考的不是“会不会背一个回溯模板”而是你对递归状态、交换顺序、重复剪枝这三件事是否真的心里有数。这篇文章我打算把这道题彻底拆开来讲包括题目到底在问什么、回溯的两条实现路线、重复字符怎么去重、字典序返回的要求以及面试时有哪些值得提前准备的变形。适合正在刷剑指Offer找工作的同学也适合被回溯题劝退、看到递归就头大的新手。整道题吃透之后你会发现很多排列、组合、子集、括号生成问题本质都是同一个套路。1. 题目到底在问什么一个全排列问题为什么能难住人1.1 描述与示例看似简单的输出题题面非常简洁输入一个字符串打印出该字符串中字符的所有排列。比如输入字符串abc输出应该是abc、acb、bac、bca、cab、cba一共 6 种。但千万不要被这个简单的描述骗了。原题有两个隐藏条件一个比一个关键第一输入字符串可能包含重复字符。如果输入aab全排列不是 6 种而是 3 种aab、aba、baa。如何在递归过程中避免重复结果这是本题真正的分水岭。第二输出要求按照字典序排序。剑指Offer原书明确要求“按字典序排列”比如输入baa返回的应该是[aab, aba, baa]而不是任意顺序。很多解法跑通了平台用例却没有处理字典序严格来说并不能算完全通过。1.2 排列数的规模为什么不能用穷举从数学上看一个长度为 n 的、所有字符互不相同的字符串全排列数量是 n! 个。3 个字符是 64 个字符是 245 个字符是 120一旦到 10 个字符就是 3628800。这个增长速度非常夸张意味着你不能靠写一堆嵌套循环去枚举必须用递归把大问题拆成小问题。这里有个直观的拆法固定第一个字符剩下的子串继续做全排列。比如abc先固定a那么问题变成求bc的排列固定b问题变成求ac的排列固定c问题变成求ab的排列。递归的终止条件是子串只剩下一个字符。这种“固定一位递归处理剩余位”的思路就是回溯法的雏形。1.3 这道题真正想考察的三件事面试官问这道题通常不是想看你会不会调用next_permutation而是想看三件事递归状态管理、回溯时的状态恢复、重复结果剪枝。状态管理对应的是每一层递归里你如何知道哪些字符已经被用过是维护一个used布尔数组还是在原字符串上做交换状态恢复对应的是递归返回上一层后你能不能把数组或路径还原成进入递归前的样子从而不影响下一次尝试重复剪枝对应的是aab这类输入你怎么保证两个a不会带来重复分支这三件事每一件都有对应的常见错误。接下来我从两条主流实现路线开始讲。2. 两种回溯姿势填位置法 vs 原书交换法2.1 填位置法维护used数组逐步选择第一种思路非常接近人类直觉把排列看成“往 n 个空位里填字符”。为了知道哪些字符已经填过额外维护一个长度为 n 的used数组used[i] true表示下标 i 的字符已经在当前路径中被使用。递归到第index层时遍历整个字符串遇到没用过的字符就放进path标记为已用递归处理下一层返回后再撤销。以abc为例第一层尝试填a进入第二层第二层不能再用a于是尝试b进入第三层第三层只剩c填完后得到abc。然后一路回溯回到第二层把b的使用标记撤销尝试c得到acb。这个过程画成递归树非常清晰路径上的字符组合就是一个排列。填位置法的优点是逻辑直观不容易漏状态。缺点是每次递归都要从头到尾扫描一遍字符串而且需要维护额外的path和used数组。2.2 交换法原字符串上做交换和恢复剑指Offer原书用的是另一种思路不额外构造路径直接在原字符串上交换。对于当前位置index遍历从index到末尾的所有位置i把s[i]换到s[index]然后递归处理index 1到末尾的子串。递归返回后再把两个位置换回来恢复原状。代码骨架长这样void dfs(string s, int index, vectorstring res) { if (index s.size() - 1) { res.push_back(s); return; } for (int i index; i s.size(); i) { swap(s[index], s[i]); dfs(s, index 1, res); swap(s[index], s[i]); // 恢复现场 } }这段代码是很多人的启蒙版本。问题也随之而来它没有做任何去重输入aab会输出 6 个结果其中有大量重复。2.3 为什么交换法一定要恢复现场这是最容易犯迷糊的地方。假设现在在index 0层先把s[1]和s[0]交换abc变成bac然后递归生成了所有以b开头的排列。递归返回后如果你不把两个字符换回来下一次循环i 2时你要把c换到首位但此时字符串已经不是最初的abc而是bac交换后变成cab。看起来也能生成c开头的排列但整体状态被打乱了结果会出现重复和缺失。打个比方这就像你在拼一把数字锁试过一种组合后必须把转轮拨回原位再去试下一种。如果不回位后面的尝试全部建立在错误状态之上。交换法里的第二次swap就是“拨回原位”这个动作它保证了同一层循环里的每次尝试都基于同一个初始字符串。2.4 面试时我推荐你用哪种如果是面试白板我更推荐交换法原因很实在剑指Offer原书用的是交换法面试官看到你的代码会更有熟悉感追问时也更容易顺着原书思路展开。而且交换法不需要额外构造path和used代码更短出错点更少。但如果你对交换法的“恢复现场”缺乏信心填位置法也不是不行。填位置法胜在逻辑上更接近“选一个字符、递归、撤销选择”的标准回溯模板面试官同样认可。关键在于无论选哪种你都必须能把“状态如何转移、如何撤销”讲清楚。3. 重复字符陷阱从“结果去重”到“递归剪枝”的完整演进3.1 直接跑交换法会得到什么我用交换法跑aab如果不去重得到的 6 个结果里aab出现两次aba出现两次baa出现两次。为什么呢因为两个a虽然字符相同但它们在字符串中的下标不同。交换s[0]和s[1]得到aab不交换直接递归也是aab于是同一个排列被两条路径同时生成。这个问题不是个例。任何包含重复字符的输入都会产生大量重复排列并且重复数量随相同字符个数增长。如果不处理生成的结果集会比正确答案大好几倍甚至十几倍。3.2 方案一放进Set统一去重为什么一定要写对最省事的想法是先把所有结果放进unordered_set最后再转成vector。代码只要在递归终止时写set.insert(s)最后遍历set加入结果数组就行。这个方案能通过平台用例但我不建议在面试中作为最终答案。原因有两点第一它没有在递归过程中剪枝重复分支照样完整展开当输入字符串比较长时白白浪费大量时间第二面试官接下来一定会追问“如果输入是 20 个字符这个方案能扛住吗”你很难给出漂亮回答。不过Set去重作为一种保底方案价值在于帮你快速验证思路尤其是递归状态已经比较复杂的时候。先把功能跑通再优化去重这个节奏没有问题。3.3 方案二排序后跳过相邻重复字符为什么常常写错另一种常见思路是先把字符串排序让相同字符相邻然后在同一层循环中如果s[i] s[i - 1]就跳过。这个想法本身没错但直接套到交换法上会出大问题。因为交换法会不断改变字符串中字符的顺序排序只在一开始执行一次后面字符串早就乱序了s[i]和s[i - 1]是否相邻已经不能代表“同一层是否已经用过相同字符”。比如aab排序后是aab在index 0层第一轮不交换递归得到aab等结果。第二轮i 1此时s[1]是a你看到s[1] s[0]就直接跳过这确实避免了重复但到了下一层index 1字符串可能已经被前面的交换改成了aba此时s[1]是bs[0]是a相邻重复判断根本不适用。这个问题非常隐蔽刷题时容易踩坑。3.4 正解同层去重的完整原理与实现正确做法要抓住一个原则在同一层递归中同一个字符只能被放到当前位置一次。这里“同一层”是指index相同的那一层循环只要某个字符在本次循环中已经换到过index位置后面再遇到相同字符就直接跳过。交换法里实现方式是维护一个局部unordered_setchar swapped每轮循环把当前要换到index的字符加进去如果swapped中已经存在该字符说明这个字符在这一层已经被处理过跳过。核心代码void dfs(string s, int index, vectorstring res) { if (index s.size() - 1) { res.push_back(s); return; } unordered_setchar swapped; for (int i index; i s.size(); i) { if (swapped.count(s[i])) continue; swapped.insert(s[i]); swap(s[index], s[i]); dfs(s, index 1, res); swap(s[index], s[i]); } }这里有个细节要说明unordered_set必须在递归函数内部、每次调用时重新创建。如果把它定义成成员变量或全局变量所有层共用一份去重逻辑就乱了。因为每一层的“已处理字符集合”是独立的。填位置法的去重也很经典。先对字符串排序让相同字符相邻。递归循环里增加一个判断如果i 0 s[i] s[i - 1] !used[i - 1]跳过当前字符。这个条件的含义是当前字符和前一个字符相同且前一个字符刚刚被回溯释放也就是used[i - 1] false说明我们正在尝试一条和上一分支等价的路径必须剪掉。3.5 一个边界用例的完整推演aab我用交换法 同层去重推演一遍aab。index 0新建swapped集合。i 0s[0] a不在集合加入集合交换s[0]和s[0]不变递归index 1。在index 1层新建集合i 1取a交换不变递归index 2得到aab回溯后i 2取b不在集合交换得到aba递归index 2得到aba。回到index 0层循环i 1时s[1] a已经在集合里跳过i 2时s[2] b不在集合交换得到baa递归生成baa。最终结果 3 个aab、aba、baa。和数学期望完全一致。4. 完整实现与复杂度分析能通过的代码长什么样4.1 C 交换法参考实现下面给出一份完整可运行的 C 代码包含同层去重和最终排序#include vector #include string #include unordered_set #include algorithm using namespace std; class Solution { public: vectorstring Permutation(string str) { vectorstring result; if (str.empty()) { return result; } dfs(str, 0, result); sort(result.begin(), result.end()); return result; } private: void dfs(string s, int index, vectorstring result) { if (index s.size() - 1) { result.push_back(s); return; } unordered_setchar swapped; for (int i index; i s.size(); i) { if (swapped.count(s[i])) { continue; } swapped.insert(s[i]); swap(s[index], s[i]); dfs(s, index 1, result); swap(s[index], s[i]); // 恢复现场 } } };这份代码在无重复字符时也能正常工作swapped只是多了一层保险。4.2 Python 填位置法参考实现如果你是 Python 选手填位置法的实现会非常清晰from typing import List class Solution: def permutation(self, s: str) - List[str]: chars sorted(s) n len(chars) used [False] * n path [] result [] def backtrack(): if len(path) n: result.append(.join(path)) return for i in range(n): if used[i]: continue if i 0 and chars[i] chars[i - 1] and not used[i - 1]: continue used[i] True path.append(chars[i]) backtrack() used[i] False path.pop() backtrack() return result这段代码依赖两个重要前提第一chars已经排序相同字符相邻第二去重条件not used[i - 1]保证了回溯释放之后不会再次选择相同字符。如果把not used[i - 1]写成used[i - 1]结果会完全错误这个细节要格外小心。4.3 复杂度到底是多少时间复杂度的计算分两部分看。递归树的叶子节点数等于最终结果数最坏情况下所有字符互不相同是 n! 个。每条从根到叶子的路径深度是 n递归过程中每次交换在常数时间内完成所以生成所有排列的时间是 O(n * n!)。这里的因子 n 来自每层的交换操作以及最终路径构建。如果最后调用了sort还需要加上结果排序的代价 O(n! * log(n!))。当 n 比较小时影响不大但 n 超过 10 之后这个排序会明显拖慢整体速度。这也是下一章要展开讨论的点。空间复杂度主要是递归调用栈的深度 O(n)。填位置法还需要额外的path和used同样是 O(n)。结果集result本身占据 O(n * n!) 的空间这是输出规模决定的无法避免。4.4 边界条件与输入校验有几个边界条件值得单独提一下。第一输入为空字符串此时没有排列返回空列表。有些平台要求返回[]刷题时先看清题目描述。第二输入长度为 1直接返回该字符本身不需要递归。第三输入可能包含空格、数字、大小写字母混合比如aA和aa的去重要求不同。统一做法是只要字符内容相同就视为同一个字符用unordered_set去重即可不要额外依赖字符范围假设。5. 字典序返回一个被不少人忽略的硬性要求5.1 原书要求与常见误解剑指Offer原题在“输出所有排列”后面还有一句话按字典序排列。很多人在刷题平台上提交时没有这一要求于是直接丢掉这个条件。但在面试场景下面试官很可能会指着你的输出问为什么顺序是乱的字典序的本质就是字符串之间的比较规则先比较第一个字符相同则比较第二个字符以此类推。比如aab排在aba前面因为第二个字符a小于b。5.2 最后sort不行吗最省事的处理办法是递归全部结束后对result做一次sort。这个写法本身没错复杂度前面也分析过是 O(n! * log(n!))。结果集数量 n! 已经非常庞大再乘一个对数因子实际开销可能比递归生成还要高。在面试中如果你给出这个方案面试官下一步大概率会问能不能让递归天然生成字典序不用最后排序这时候你就需要掌握下面的方法。5.3 用排序预处理让递归天然有序答案是在进入递归之前先把输入字符串排序。这个预处理对交换法和填位置法都有效。填位置法的道理最直观每次循环从左到右扫描已排序的字符数组同一层尝试的字符顺序天然从小到大所以递归生成的第一个叶子就是字典序最小的排列后续叶子也按照字典序依次生成最终结果不需要额外排序。交换法稍微复杂一点。排序只是让初始字符串有序但交换过程会打乱顺序。如果你希望结果天然字典序需要保证同一层循环里交换到index位置的字符从左到右递增。交换法里用unordered_set去重时字符尝试顺序是按原始下标顺序来的排序之后的原始顺序就是字典序所以大多数情况下也能得到有序输出。但为了稳妥尤其是面对平台用例时我会在返回前补一个sort。这算是在代码简洁性和性能之间取一个平衡。6. 从这道题延伸出去回溯模板与面试官的花式追问6.1 一个能通杀排列组合子集的回溯骨架字符串的排列本质上是一道标准的回溯题。我把这类题的通用骨架总结成三步选择、递归、撤销。选择指的是在当前状态做出一个决策比如把某个字符放到当前位置递归指的是把决策后的状态传给子问题继续尝试撤销指的是递归返回以后把状态恢复成进入递归之前的样子从而让同一层的其他决策也能在正确的起点上继续。这个骨架可以套用到很多题目上LeetCode 46全排列、LeetCode 77组合、LeetCode 78子集、LeetCode 22括号生成、LeetCode 51N皇后。区别只在于决策的范围、终止条件、剪枝条件不同。你能把字符串的排列吃透后面遇到这些题会轻松很多。6.2 面试中常见的三个变体面试官很可能会在基本题之上做变形我整理了三个高频变体供你提前准备。第一个变体只输出长度为 k 的排列而不是全部排列。解法是给递归增加一个depth k的终止条件其余逻辑完全不变。第二个变体允许字符重复使用比如输入abc输出长度为 3 的可重复排列aaa、aab等。这时不能再依靠used数组去重因为同一个字符可以在不同位置重复出现。正确的改动是每次递归都从头开始尝试所有字符去掉used标记即可。第三个变体要求返回第 k 个字典序排列。这是LeetCode 60的经典题不能用回溯硬搜因为 n 很大时会超时。正确思路是用阶乘数系逐位定位第一位确定后剩余排列数量是 (n-1)!用 k 除以 (n-1)! 得到当前位取第几个候选字符然后更新 k 为余数。这个变体考察的是数学推导能力面试中属于加分项。6.3 给刷题人的几条实际操作建议第一不要跳过画递归树。画一次胜过看十遍代码。拿abc和aab各画一棵树你才能直观看到重复分支出现在哪里剪枝条件为什么这样写。第二去重的原理一定要能用自己的话说清楚。面试官最爱问的一句话是你这句去重条件为什么这样写能回答出“同一层递归中相同字符只允许被选择一次”比代码本身更有说服力。第三写完代码一定要验一个重复字符用例。很多人写完直接拿abc跑一遍发现 6 个结果正确就提交了完全没检查aab这种输入。提醒自己养成这个习惯能避免大量本可以避免的返工。第四如果你在面试中真的卡住了不要硬写。先坦诚地和面试官说“我先用 Set 去重写一版确认功能正确再优化剪枝。”这个策略既能保证代码可运行又能展示你具备优化意识比闷头写一个错误答案要好得多。我自己最开始学这题时栽就栽在没搞懂为什么要交换两次。后来把递归树一笔一笔画在草稿纸上才真正明白回溯的本质就是“试错、恢复、再试另一个”。字符串的排列就像一把钥匙吃透它之后很多回溯题都会变得顺理成章。希望这篇文章能帮你少走我走过的弯路把这把钥匙真正握在手里。