企业官网建设流程全解析

如果你刷过一段时间剑指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 个字符是 6，4 个字符是 24，5 个字符是 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, vector<string>& 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]是b，s[0]是a，相邻重复判断根本不适用。这个问题非常隐蔽，刷题时容易踩坑。

3.4 正解：同层去重的完整原理与实现

正确做法要抓住一个原则：在同一层递归中，同一个字符只能被放到当前位置一次。这里“同一层”是指index相同的那一层循环；只要某个字符在本次循环中已经换到过index位置，后面再遇到相同字符就直接跳过。

交换法里，实现方式是维护一个局部unordered_set<char> swapped，每轮循环把当前要换到index的字符加进去；如果swapped中已经存在该字符，说明这个字符在这一层已经被处理过，跳过。核心代码：

void dfs(string& s, int index, vector<string>& res) { if (index == s.size() - 1) { res.push_back(s); return; } unordered_set<char> 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 = 0，s[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: vector<string> Permutation(string str) { vector<string> result; if (str.empty()) { return result; } dfs(str, 0, result); sort(result.begin(), result.end()); return result; } private: void dfs(string& s, int index, vector<string>& result) { if (index == s.size() - 1) { result.push_back(s); return; } unordered_set<char> 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 去重写一版，确认功能正确，再优化剪枝。”这个策略既能保证代码可运行，又能展示你具备优化意识，比闷头写一个错误答案要好得多。

我自己最开始学这题时，栽就栽在没搞懂为什么要交换两次。后来把递归树一笔一笔画在草稿纸上，才真正明白回溯的本质就是“试错、恢复、再试另一个”。字符串的排列就像一把钥匙，吃透它之后，很多回溯题都会变得顺理成章。希望这篇文章能帮你少走我走过的弯路，把这把钥匙真正握在手里。