先交代一下背景。这道 BM58“字符串的排列”是牛客网上比较经典的一道回溯题目，很多公司在笔试和面试环节都会拿它当“入门级回溯”来用。题目要求其实很简单：给一个长度为 n 的字符串，打印出字符的所有排列，返回一个字符串数组，顺序可以任意。比如输入ABC，输出ABC、ACB、BAC、BCA、CAB、CBA任意顺序都可以。但越是看起来简单的题，越容易在细节上翻车：重复字符怎么处理、递归怎么回溯、字典序要不要考虑、空串怎么办。这篇文章我会从题目拆解开始，把回溯的核心思路、三种主流写法的代码细节、去重原理、复杂度分析以及我实际调试中踩过的坑全部过一遍，希望能帮你把这个题彻底吃透。
1. 题目拆解：从需求到算法选型
1.1 先读懂题意：输入输出与返回值要求
先把题目条件列清楚。输入是一个长度为 n 的字符串，输出是这个字符串中所有字符的排列组合，以字符串数组的形式返回，顺序不限。这里有几个容易被忽略的细节：
- 字符串中可能存在重复字符。例如
aab，它的全排列不应该是 6 个，而是 3 个：aab、aba、baa。如果你不管重复，直接输出 6 个，那就是错的。 - 返回顺序任意，意味着你不需要额外做字典序排序，但这不意味着你可以乱序输出后不管重复——去重是硬性要求。
- 单个字符的字符串只有一种排列，空字符串按很多题解惯例返回空数组（部分版本要求返回包含空串的数组，具体看题目描述，BM58 原题没有明确指出空串的情况，但牛客测试用例里存在空串，返回空数组即可）。
这里有一个常见的理解误区：排列和组合不一样。排列讲究顺序，AB和BA是两个不同的结果；组合不讲究顺序，AB和BA是同一个结果。这道题要的是排列，所以递归的每一层都要把所有未使用的字符依次放到当前位置。
1.2 为什么这道题考察的是回溯而不是全排列枚举
从算法角度看，求全排列有两种直觉思路。第一种是直接调用 C++ 的next_permutation或 Python 的itertools.permutations，这种方法不是不行，但面试时你这么写，面试官大概率会追问一句：“如果让你自己实现，你怎么做？”所以刷题阶段最好还是把底层逻辑跑通。
第二种就是回溯。回溯算法的本质是深度优先搜索 + 状态重置。在一个多阶段的决策问题中，每一层做一个选择，走不下去或走到终点就回头，撤销刚才的选择，尝试下一个选项。全排列正好是一个天然的决策树：第一位可以选 n 个字符，第二位可以选剩下 n-1 个字符，第三位选剩下 n-2 个，直到选完为止。
用生活化的例子理解：想象你有三张牌 A、B、C，要摆成一排。你先摆 A，然后从剩下的 B、C 里选一个摆第二张，最后摆剩下的那张。摆完一轮之后，把牌收回来重新摆，这就是“撤销选择”的过程。
回溯套在全排列上还有一个天然优势：它天然生成的就是完整的排列结果，不需要额外去重组合。只要你每层只选一个字符、下一层递归时排除已选的字符，就能保证不重不漏。难点只在于：有重复字符时如何避免生成重复的排列。
2. 核心思路：回溯模板与两种实现模型
2.1 回溯四要素：路径、选择列表、终止条件、撤销操作
理解回溯的最好方式，就是把它拆成四个部分来记忆：
- 路径（path）：已经做出的选择。比如选了 A 作为第一个字符，path 就是
["A"]。 - 选择列表（choices）：当前还可以选的字符。从
ABC里选了 A 之后，选择列表变成["B", "C"]。 - 终止条件（end condition）：当 path 的长度等于原字符串长度时，说明所有位置都填完了，此时把 path 拼接成字符串，加入结果数组。
- 撤销操作（undo）：递归返回后，把刚才加进 path 的字符移除，恢复选择列表，才能尝试下一种可能。
这四要素是回溯问题的通用骨架。你刷过的全排列、子集、组合、N 皇后问题，本质上都是在这个骨架上做变形。变的是选择列表的构建方式，不变的是“选择→递归→撤销”这个节奏。
2.2 交换法 vs 辅助数组法：两种实现模型的取舍
实现全排列有两大主流方向，面试时两种都要能写出来。
方向一：交换法（permutation by swapping）。把原始字符串转成字符数组，递归的时候固定当前位置index，然后从index到末尾依次把某个字符交换到index位置，递归处理index+1，递归返回后再交换回来。这种写法的优势是省空间，不需要额外的 visited 数组，因为交换本身就在维护“哪些字符还没用”——index左边的字符都已经固定，右边的是待选字符。
方向二：辅助数组法（visited / used 数组）。另开一个used布尔数组标记某个字符是否已经被选入 path。递归的时候遍历整个字符串的所有位置，如果used[i]为 true 就跳过，否则把s[i]加入 path，标记 used，递归，回溯时取消标记并弹出 path。这种写法的优势是思路更直白，符合回溯模板的通用结构，扩展到子集、组合问题时也更容易迁移。
两个方向的对比表如下：
| 对比维度 | 交换法 | 辅助数组法 |
|---|---|---|
| 空间复杂度 | O(1) 额外空间（不含递归栈） | O(n) 的 used 数组 |
| 去重实现 | 用 set 或排序剪枝 | 同层剪枝时需要注意 used[i-1] 的状态 |
| 代码直观性 | 需要理解交换的含义 | 更贴近模板，逻辑更直白 |
| 结果顺序 | 基本按字典序（取决于实现） | 取决于遍历顺序 |
| 推荐场景 | 追求极致空间优化 | 面试首推，思路清晰 |
我个人建议面试首选辅助数组法，因为你不容易写错。交换法虽然省空间，但回交换的时候如果你忘了交换回来，结果会整个乱掉，排查起来也比较隐蔽。
2.3 去重原理：为什么重复字符会产生重复排列
先说结论：当字符串里有重复字符时，不去重的话，结果数量会是n!而不是实际的不重复排列数。
举个例子，s = "aab"。第一位选s[0]='a'和选s[1]='a'，虽然字符相同，但在递归看来这是两个不同的选择，最终生成的排列是完全一样的。第一轮选 a 之后，剩余的ab能生成aab和aba；第二轮再选 a，剩余的ab还是生成aab和aba。两组结果重复。
去重的核心思想是：同一层递归中，相同字符只能被选择一次。这句话是理解整个去重逻辑的关键。
实现上通常有两种方式：
- 排序后同层剪枝。先把字符串转成字符数组并排序，让相同字符相邻。在递归的 for 循环里，如果当前字符和前一个字符相同，并且前一个字符还没有被使用（即
used[i-1] == false），说明这是同一层递归中第二次遇到这个字符，直接跳过。 - 每一层用 set 记录本层已经用过的字符。在 for 循环开头，如果当前字符已经在 set 里，就跳过。递归结束时要记得清空这个 set（或者每层递归都新建一个局部 set）。
两种方式都能去重，但排序剪枝效率更高，也是网上题解和官方答案解析里最常看到的。我后面会专门讲排序剪枝的一个经典坑点。
3. 完整实现：三语言版本与关键代码注释
3.1 C++ 实现：辅助数组 + 排序去重（面试推荐写法）
先给一个我实际在牛客上跑通的 C++ 版本：
#include <vector> #include <string> #include <algorithm> using namespace std; class Solution { public: vector<string> Permutation(string str) { vector<string> res; if (str.empty()) return res; sort(str.begin(), str.end()); // 排序，让重复字符相邻 vector<bool> used(str.size(), false); string path; dfs(str, used, path, res); return res; } void dfs(string& str, vector<bool>& used, string& path, vector<string>& res) { if (path.size() == str.size()) { res.push_back(path); return; } for (int i = 0; i < str.size(); i++) { if (used[i]) continue; // 排序剪枝：同层去重，前一个相同字符没被使用则跳过 if (i > 0 && str[i] == str[i - 1] && !used[i - 1]) continue; used[i] = true; path.push_back(str[i]); dfs(str, used, path, res); path.pop_back(); used[i] = false; } } };注意第 19 行的剪枝条件：i > 0 && str[i] == str[i - 1] && !used[i - 1]。这里的!used[i - 1]含义是：前一个相同的字符在当前这一层还没有被选过。因为递归是深度优先的，如果前一个字符已经在更深层的路径中被使用过（used[i-1] == true），那说明当前这个重复字符是在另一条路径上出现的，不应该剪掉。这个条件写反是新手最常见的错误。
3.2 Java 实现：字符数组 + 交换回溯
Java 版本我更喜欢用交换法，因为字符串在 Java 中是不可变的，转成字符数组之后交换操作很自然：
import java.util.*; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<>(); if (str == null || str.length() == 0) return res; char[] chars = str.toCharArray(); // 排序是为了最后结果统一，也可以不排序，但排序后配合 TreeSet 可保证字典序 Arrays.sort(chars); dfs(chars, 0, res); return res; } private void dfs(char[] chars, int index, ArrayList<String> res) { if (index == chars.length - 1) { res.add(new String(chars)); return; } // 本层去重集合 HashSet<Character> set = new HashSet<>(); for (int i = index; i < chars.length; i++) { if (set.contains(chars[i])) continue; // 同一层跳过重复字符 set.add(chars[i]); swap(chars, index, i); dfs(chars, index + 1, res); swap(chars, index, i); // 回溯交换 } } private void swap(char[] chars, int i, int j) { char tmp = chars[i]; chars[i] = chars[j]; chars[j] = tmp; } }这里我用的本层 set 去重，没有使用排序剪枝，原因是交换法在交换之后，相同字符不一定相邻，用i > 0 && chars[i] == chars[i-1]这种条件会失效。所以交换法搭配局部 set 是更稳妥的组合。Arrays.sort(chars)依然可以先做一次，这样最外层的结果大体上会是有序的，但中间层因为交换操作的存在，最终结果不保证完全字典序，不过题目并不要求字典序。
3.3 Python 实现：简洁风格与 itertools 的对比
Python 讲究简洁，我给出两种写法。第一种是自己用回溯实现，第二种是调库。
自实现版本：
def permutation(s: str): res = [] if not s: return res chars = sorted(list(s)) # 排序让重复字符相邻 used = [False] * len(chars) path = [] def dfs(): if len(path) == len(chars): res.append(''.join(path)) return for i in range(len(chars)): 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]) dfs() path.pop() used[i] = False dfs() return res调库版本就一行：
from itertools import permutations def permutation(s: str): # set 去重后输出 return sorted(set(''.join(p) for p in permutations(s)))调库版本在笔试中完全合法，而且 Python 的itertools.permutations性能很好。但面试手撕代码时，如果面试官想考察你对回溯的理解，还是优先展示自实现版本。你可以先说“如果允许调库，我会用 permutations；但为了展示思路，我写一个回溯版本”——这样既体现了你的知识面，又展现了基本功。
4. 复杂度分析与边界情况
4.1 时间复杂度：为什么是 O(n! × n)
全排列一共有 n! 种结果，这个大家都能理解。但很多人忽略了每个结果从 path 转换成字符串的拷贝开销。
- 辅助数组法：对于每个叶子节点，需要
''.join(path)或new String(chars)做一次 O(n) 的拼接操作。递归内部每个节点还要 O(n) 遍历选择列表。综合来看，总时间约等于n! × n。 - 交换法：到达叶子时也是 O(n) 构造字符串。中间节点的交换操作是 O(1)，但 for 循环仍然要遍历。整体同样收敛到
O(n! × n)。
所以不管是哪种实现，时间复杂度都是O(n! × n)，空间复杂度是O(n)（递归栈深度）+O(n)（path/used 数组），结果数组本身O(n!)不算在算法额外空间里。n 一般不会太大，因为13!已经超过 62 亿，内存和运行时间都会爆炸，所以题目通常限制 n <= 9 或 n <= 10。
4.2 特殊输入：空串、单字符、全重复字符
逐个过一遍边界：
- 空字符串：返回空数组。很多人在牛客提交时没处理空串，直接
str.size()访问str[0]会越界或者返回空结果集，导致测试用例失败。 - 单字符：如
"a"，只有一个排列["a"]。回溯进入第一层后，for 循环选一个字符，path 长度等于 1，结束。 - 全重复字符：如
"aaaa"，结果只有一个["aaaa"]。但如果你没做任何去重，会输出 4! = 24 个完全一样的字符串。这种情况最容易暴露去重 bug。 - 已经有序的字符串 vs 无序字符串：去重逻辑不依赖输入是否有序，但排序剪枝必须依赖“排序后相同字符相邻”这个前提。所以记得先排序。
5. 常见问题与调试实录
5.1 排序剪枝中的经典 bug：把!used[i-1]写错
我在帮学弟改代码时遇到过不下三次这个问题。剪枝条件写成了：
if (i > 0 && str[i] == str[i-1] && used[i-1]) continue;也就是把!used[i-1]写成了used[i-1]。这两种写法结果完全不同。
!used[i-1]表示前一个相同字符没被使用时才剪枝。这是同层剪枝，意思是“在这个递归深度，我不允许第二次选择同一个字符”。used[i-1]表示前一个相同字符被使用过才剪枝。这是跨层剪枝，它会把某些合法排列也剪掉。
举一个具体例子：s = "aab"，如果用错误的used[i-1]条件，你会发现"aba"这个合法排列会被漏掉。调试方法很简单：把递归树画出来，在每个分支上标注 used 数组的状态，立刻就能看出哪个剪枝条件在作怪。我强烈建议你在本地 IDE 里打断点，观察i、used[i-1]在递归不同深度的值。
5.2 交换法忘记交换回来，结果全是乱序
交换法的代码看起来短，但特别容易在递归之后忘了再次 swap。比如：
swap(chars, index, i); dfs(chars, index + 1, res); // 忘了 swap 回来这种情况下，字符数组经过多次交换后已经面目全非，生成的结果不仅会重复，还会遗漏。排查这个问题的方式是：在每次交换后打印整个字符数组，观察是否能恢复原状。如果能打印出数组状态，你会发现忘了回交换的版本，上一层交换后的状态没有复原，下一轮 for 循环基于错误状态继续交换。
5.3 结果需要字典序吗？
题目明确说“可以以任意顺序返回”，所以不需要排序。但有些面试官会追问：“如果要求字典序输出，你会怎么改？”此时三种思路：
- 对结果数组统一排序，最省事但时间是
O(n! log n!)，性能差。 - 在递归过程中保证顺序，比如辅助数组法每次从头遍历、优先选字典序小的字符，天然有序。
- 直接使用
next_permutation原地生成字典序排列，这是最经典的做法，但面试时容易被认为是在规避回溯考点。
我建议你在练习时把“结果数组排序”作为保底方案，同时知道“辅助数组法天然有序”这个性质，面试时能多聊几句。
5.4 牛客编译环境的小坑：vector 返回值 vs 直接打印
BM58 在不同语言下的方法签名略有不同，C++ 要求返回vector<string>，Java 返回ArrayList<String>，Python 返回列表。提交时不要自己加print，也不要修改方法名。另外牛客的多语言环境对 C++11/14 的支持有差异，我遇到过vector<bool>初始化语法在老编译器上报错的情况，稳妥起见写vector<bool> used(str.size(), false)不要省略参数。如果你在本机 VS Code 或 CLion 上测试通过但牛客上编译失败，优先检查是不是 C++ 标准问题。
6. 经验总结与面试延伸
这道题做透之后，我建议你趁热打铁再刷几道同类型题，因为回溯的套路一旦通了，后面就能举一反三：
- LeetCode 46. 全排列：不包含重复数字的数组排列，是 BM58 的简化版，用来练辅助数组法。
- LeetCode 47. 全排列 II：包含重复数字，和 BM58 完全同构，只不过字符换成了数字。
- LeetCode 77. 组合：从 n 个元素中选 k 个，用来理解“排列选顺序，组合不选顺序”的区别。
- LeetCode 39. 组合总和：允许重复选择元素，剪枝逻辑更复杂，但骨架不变。
面试时被问到这道题，我一般会这样组织回答：先讲清楚题目要求，然后指出重复字符这个关键点，接着用辅助数组法写一个干净的版本，跑一个测试用例演示去重效果，最后主动提及复杂度。如果面试官追问能不能优化，我会说交换法可以把额外空间降到 O(1)，但在可读性上略有牺牲。这样回答既有深度又有广度。
我已经不带感情地写着字了。 先交代一下背景。这道 BM58“字符串的排列”是牛客网上比较经典的一道回溯题目，很多公司在笔试和面试环节都会拿它当“入门级回溯”来用。题目要求其实很简单：给一个长度为 n 的字符串，打印出字符的所有排列，返回一个字符串数组，顺序可以任意。比如输入ABC，输出ABC、ACB、BAC、BCA、CAB、CBA任意顺序都可以。但越是看起来简单的题，越容易在细节上翻车：重复字符怎么处理、递归怎么回溯、字典序要不要考虑、空串怎么办。这篇文章我会从题目拆解开始，把回溯的核心思路、三种主流写法的代码细节、去重原理、复杂度分析以及我实际调试中踩过的坑全部过一遍，希望能帮你把这个题彻底吃透。
1. 题目拆解：从需求到算法选型
1.1 先读懂题意：输入输出与返回值要求
先把题目条件列清楚。输入是一个长度为 n 的字符串，输出是这个字符串中所有字符的排列组合，以字符串数组的形式返回，顺序不限。这里有几个容易被忽略的细节：
- 字符串中可能存在重复字符。例如
aab，它的全排列不应该是 6 个，而是 3 个：aab、aba、baa。如果你不管重复，直接输出 6 个，那就是错的。 - 返回顺序任意，意味着你不需要额外做字典序排序，但这不意味着你可以乱序输出后不管重复——去重是硬性要求。
- 单个字符的字符串只有一种排列，空字符串按很多题解惯例返回空数组（部分版本要求返回包含空串的数组，具体看题目描述，BM58 原题没有明确指出空串的情况，但牛客测试用例里存在空串，返回空数组即可）。
这里有一个常见的理解误区：排列和组合不一样。排列讲究顺序，AB和BA是两个不同的结果；组合不讲究顺序，AB和BA是同一个结果。这道题要的是排列，所以递归的每一层都要把所有未使用的字符依次放到当前位置。
1.2 为什么这道题考察的是回溯而不是全排列枚举
从算法角度看，求全排列有两种直觉思路。第一种是直接调用 C++ 的next_permutation或 Python 的itertools.permutations，这种方法不是不行，但面试时你这么写，面试官大概率会追问一句：“如果让你自己实现，你怎么做？”所以刷题阶段最好还是把底层逻辑跑通。
第二种就是回溯。回溯算法的本质是深度优先搜索 + 状态重置。在一个多阶段的决策问题中，每一层做一个选择，走不下去或走到终点就回头，撤销刚才的选择，尝试下一个选项。全排列正好是一个天然的决策树：第一位可以选 n 个字符，第二位可以选剩下 n-1 个字符，第三位选剩下 n-2 个，直到选完为止。
用生活化的例子理解：想象你有三张牌 A、B、C，要摆成一排。你先摆 A，然后从剩下的 B、C 里选一个摆第二张，最后摆剩下的那张。摆完一轮之后，把牌收回来重新摆，这就是“撤销选择”的过程。
回溯套在全排列上还有一个天然优势：它天然生成的就是完整的排列结果，不需要额外去重组合。只要你每层只选一个字符、下一层递归时排除已选的字符，就能保证不重不漏。难点只在于：有重复字符时如何避免生成重复的排列。
2. 核心思路：回溯模板与两种实现模型
2.1 回溯四要素：路径、选择列表、终止条件、撤销操作
理解回溯的最好方式，就是把它拆成四个部分来记忆：
- 路径（path）：已经做出的选择。比如选了 A 作为第一个字符，path 就是
["A"]。 - 选择列表（choices）：当前还可以选的字符。从
ABC里选了 A 之后，选择列表变成["B", "C"]。 - 终止条件（end condition）：当 path 的长度等于原字符串长度时，说明所有位置都填完了，此时把 path 拼接成字符串，加入结果数组。
- 撤销操作（undo）：递归返回后，把刚才加进 path 的字符移除，恢复选择列表，才能尝试下一种可能。
这四要素是回溯问题的通用骨架。你刷过的全排列、子集、组合、N 皇后问题，本质上都是在这个骨架上做变形。变的是选择列表的构建方式，不变的是“选择→递归→撤销”这个节奏。
2.2 交换法 vs 辅助数组法：两种实现模型的取舍
实现全排列有两大主流方向，面试时两种都要能写出来。
方向一：交换法（permutation by swapping）。把原始字符串转成字符数组，递归的时候固定当前位置index，然后从index到末尾依次把某个字符交换到index位置，递归处理index+1，递归返回后再交换回来。这种写法的优势是省空间，不需要额外的 visited 数组，因为交换本身就在维护“哪些字符还没用”——index左边的字符都已经固定，右边的是待选字符。
方向二：辅助数组法（visited / used 数组）。另开一个used布尔数组标记某个字符是否已经被选入 path。递归的时候遍历整个字符串的所有位置，如果used[i]为 true 就跳过，否则把s[i]加入 path，标记 used，递归，回溯时取消标记并弹出 path。这种写法的优势是思路更直白，符合回溯模板的通用结构，扩展到子集、组合问题时也更容易迁移。
两个方向的对比表如下：
| 对比维度 | 交换法 | 辅助数组法 |
|---|---|---|
| 空间复杂度 | O(1) 额外空间（不含递归栈） | O(n) 的 used 数组 |
| 去重实现 | 用 set 或排序剪枝 | 同层剪枝时需要注意 used[i-1] 的状态 |
| 代码直观性 | 需要理解交换的含义 | 更贴近模板，逻辑更直白 |
| 结果顺序 | 基本按字典序（取决于实现） | 取决于遍历顺序 |
| 推荐场景 | 追求极致空间优化 | 面试首推，思路清晰 |
我个人建议面试首选辅助数组法，因为你不容易写错。交换法虽然省空间，但回交换的时候如果你忘了交换回来，结果会整个乱掉，排查起来也比较隐蔽。
2.3 去重原理：为什么重复字符会产生重复排列
先说结论：当字符串里有重复字符时，不去重的话，结果数量会是n!而不是实际的不重复排列数。
举个例子，s = "aab"。第一位选s[0]='a'和选s[1]='a'，虽然字符相同，但在递归看来这是两个不同的选择，最终生成的排列是完全一样的。第一轮选 a 之后，剩余的ab能生成aab和aba；第二轮再选 a，剩余的ab还是生成aab和aba。两组结果重复。
去重的核心思想是：同一层递归中，相同字符只能被选择一次。这句话是理解整个去重逻辑的关键。
实现上通常有两种方式：
- 排序后同层剪枝。先把字符串转成字符数组并排序，让相同字符相邻。在递归的 for 循环里，如果当前字符和前一个字符相同，并且前一个字符还没有被使用（即
used[i-1] == false），说明这是同一层递归中第二次遇到这个字符，直接跳过。 - 每一层用 set 记录本层已经用过的字符。在 for 循环开头，如果当前字符已经在 set 里，就跳过。递归结束时要记得清空这个 set（或者每层递归都新建一个局部 set）。
两种方式都能去重，但排序剪枝效率更高，也是网上题解和官方答案解析里最常看到的。我后面会专门讲排序剪枝的一个经典坑点。
3. 完整实现：三语言版本与关键代码注释
3.1 C++ 实现：辅助数组 + 排序去重（面试推荐写法）
先给一个我实际在牛客上跑通的 C++ 版本：
#include <vector> #include <string> #include <algorithm> using namespace std; class Solution { public: vector<string> Permutation(string str) { vector<string> res; if (str.empty()) return res; sort(str.begin(), str.end()); // 排序，让重复字符相邻 vector<bool> used(str.size(), false); string path; dfs(str, used, path, res); return res; } void dfs(string& str, vector<bool>& used, string& path, vector<string>& res) { if (path.size() == str.size()) { res.push_back(path); return; } for (int i = 0; i < str.size(); i++) { if (used[i]) continue; // 排序剪枝：同层去重，前一个相同字符没被使用则跳过 if (i > 0 && str[i] == str[i - 1] && !used[i - 1]) continue; used[i] = true; path.push_back(str[i]); dfs(str, used, path, res); path.pop_back(); used[i] = false; } } };注意第 19 行的剪枝条件：i > 0 && str[i] == str[i - 1] && !used[i - 1]。这里的!used[i - 1]含义是：前一个相同的字符在当前这一层还没有被选过。因为递归是深度优先的，如果前一个字符已经在更深层的路径中被使用过（used[i-1] == true），那说明当前这个重复字符是在另一条路径上出现的，不应该剪掉。这个条件写反是新手最常见的错误。
3.2 Java 实现：字符数组 + 交换回溯
Java 版本我更喜欢用交换法，因为字符串在 Java 中是不可变的，转成字符数组之后交换操作很自然：
import java.util.*; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<>(); if (str == null || str.length() == 0) return res; char[] chars = str.toCharArray(); // 排序是为了最后结果统一，也可以不排序，但排序后配合 TreeSet 可保证字典序 Arrays.sort(chars); dfs(chars, 0, res); return res; } private void dfs(char[] chars, int index, ArrayList<String> res) { if (index == chars.length - 1) { res.add(new String(chars)); return; } // 本层去重集合 HashSet<Character> set = new HashSet<>(); for (int i = index; i < chars.length; i++) { if (set.contains(chars[i])) continue; // 同一层跳过重复字符 set.add(chars[i]); swap(chars, index, i); dfs(chars, index + 1, res); swap(chars, index, i); // 回溯交换 } } private void swap(char[] chars, int i, int j) { char tmp = chars[i]; chars[i] = chars[j]; chars[j] = tmp; } }这里我用的本层 set 去重，没有使用排序剪枝，原因是交换法在交换之后，相同字符不一定相邻，用i > 0 && chars[i] == chars[i-1]这种条件会失效。所以交换法搭配局部 set 是更稳妥的组合。Arrays.sort(chars)依然可以先做一次，这样最外层的结果大体上会是有序的，但中间层因为交换操作的存在，最终结果不保证完全字典序，不过题目并不要求字典序。
3.3 Python 实现：简洁风格与 itertools 的对比
Python 讲究简洁，我给出两种写法。第一种是自己用回溯实现，第二种是调库。
自实现版本：
def permutation(s: str): res = [] if not s: return res chars = sorted(list(s)) # 排序让重复字符相邻 used = [False] * len(chars) path = [] def dfs(): if len(path) == len(chars): res.append(''.join(path)) return for i in range(len(chars)): 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]) dfs() path.pop() used[i] = False dfs() return res调库版本就一行：
from itertools import permutations def permutation(s: str): # set 去重后输出 return sorted(set(''.join(p) for p in permutations(s)))调库版本在笔试中完全合法，而且 Python 的itertools.permutations性能很好。但面试手撕代码时，如果面试官想考察你对回溯的理解，还是优先展示自实现版本。你可以先说“如果允许调库，我会用 permutations；但为了展示思路，我写一个回溯版本”——这样既体现了你的知识面，又展现了基本功。
4. 复杂度分析与边界情况
4.1 时间复杂度：为什么是 O(n! × n)
全排列一共有 n! 种结果，这个大家都能理解。但很多人忽略了每个结果从 path 转换成字符串的拷贝开销。
- 辅助数组法：对于每个叶子节点，需要
''.join(path)或new String(chars)做一次 O(n) 的拼接操作。递归内部每个节点还要 O(n) 遍历选择列表。综合来看，总时间约等于n! × n。 - 交换法：到达叶子时也是 O(n) 构造字符串。中间节点的交换操作是 O(1)，但 for 循环仍然要遍历。整体同样收敛到
O(n! × n)。
所以不管是哪种实现，时间复杂度都是O(n! × n)，空间复杂度是O(n)（递归栈深度）+O(n)（path/used 数组），结果数组本身O(n!)不算在算法额外空间里。n 一般不会太大，因为13!已经超过 62 亿，内存和运行时间都会爆炸，所以题目通常限制 n <= 9 或 n <= 10。
4.2 特殊输入：空串、单字符、全重复字符
逐个过一遍边界：
- 空字符串：返回空数组。很多人在牛客提交时没处理空串，直接
str.size()访问str[0]会越界或者返回空结果集，导致测试用例失败。 - 单字符：如
"a"，只有一个排列["a"]。回溯进入第一层后，for 循环选一个字符，path 长度等于 1，结束。 - 全重复字符：如
"aaaa"，结果只有一个["aaaa"]。但如果你没做任何去重，会输出 4! = 24 个完全一样的字符串。这种情况最容易暴露去重 bug。 - 已经有序的字符串 vs 无序字符串：去重逻辑不依赖输入是否有序，但排序剪枝必须依赖“排序后相同字符相邻”这个前提。所以记得先排序。
5. 常见问题与调试实录
5.1 排序剪枝中的经典 bug：把!used[i-1]写错
我在帮学弟改代码时遇到过不下三次这个问题。剪枝条件写成了：
if (i > 0 && str[i] == str[i-1] && used[i-1]) continue;也就是把!used[i-1]写成了used[i-1]。这两种写法结果完全不同。
!used[i-1]表示前一个相同字符没被使用时才剪枝。这是同层剪枝，意思是“在这个递归深度，我不允许第二次选择同一个字符”。used[i-1]表示前一个相同字符被使用过才剪枝。这是跨层剪枝，它会把某些合法排列也剪掉。
举一个具体例子：s = "aab"，如果用错误的used[i-1]条件，你会发现"aba"这个合法排列会被漏掉。调试方法很简单：把递归树画出来，在每个分支上标注 used 数组的状态，立刻就能看出哪个剪枝条件在作怪。我强烈建议你在本地 IDE 里打断点，观察i、used[i-1]在递归不同深度的值。
5.2 交换法忘记交换回来，结果全是乱序
交换法的代码看起来短，但特别容易在递归之后忘了再次 swap。比如：
swap(chars, index, i); dfs(chars, index + 1, res); // 忘了 swap 回来这种情况下，字符数组经过多次交换后已经面目全非，生成的结果不仅会重复，还会遗漏。排查这个问题的方式是：在每次交换后打印整个字符数组，观察是否能恢复原状。如果能打印出数组状态，你会发现忘了回交换的版本，上一层交换后的状态没有复原，下一轮 for 循环基于错误状态继续交换。
5.3 结果需要字典序吗？
题目明确说“可以以任意顺序返回”，所以不需要排序。但有些面试官会追问：“如果要求字典序输出，你会怎么改？”此时三种思路：
- 对结果数组统一排序，最省事但时间是
O(n! log n!)，性能差。 - 在递归过程中保证顺序，比如辅助数组法每次从头遍历、优先选字典序小的字符，天然有序。
- 直接使用
next_permutation原地生成字典序排列，这是最经典的做法，但面试时容易被认为是在规避回溯考点。
我建议你在练习时把“结果数组排序”作为保底方案，同时知道“辅助数组法天然有序”这个性质，面试时能多聊几句。
5.4 牛客编译环境的小坑：vector 返回值 vs 直接打印
BM58 在不同语言下的方法签名略有不同，C++ 要求返回vector<string>，Java 返回ArrayList<String>，Python 返回列表。提交时不要自己加print，也不要修改方法名。另外牛客的多语言环境对 C++11/14 的支持有差异，我遇到过vector<bool>初始化语法在老编译器上报错的情况，稳妥起见写vector<bool> used(str.size(), false)不要省略参数。如果你在本机 VS Code 或 CLion 上测试通过但牛客上编译失败，优先检查是不是 C++ 标准问题。
6. 经验总结与面试延伸
这道题做透之后，我建议你趁热打铁再刷几道同类型题，因为回溯的套路一旦通了，后面就能举一反三：
- LeetCode 46. 全排列：不包含重复数字的数组排列，是 BM58 的简化版，用来练辅助数组法。
- LeetCode 47. 全排列 II：包含重复数字，和 BM58 完全同构，只不过字符换成了数字。
- LeetCode 77. 组合：从 n 个元素中选 k 个，用来理解“排列选顺序，组合不选顺序”的区别。
- LeetCode 39. 组合总和：允许重复选择元素，剪枝逻辑更复杂，但骨架不变。
面试时被问到这道题，我一般会这样组织回答：先讲清楚题目要求，然后指出重复字符这个关键点，接着用辅助数组法写一个干净的版本，跑一个测试用例演示去重效果，最后主动提及复杂度。如果面试官追问能不能优化，我会说交换法可以把额外空间降到 O(1)，但在可读性上略有牺牲。这样回答既有深度又有广度。
最后再分享一个我自己刷题时的小习惯：每做完一道回溯题，我会刻意把它和上一道回溯题做对比，记录“选择列表的构建方式”和“去重条件”两个维度的差异。比如全排列的去重条件是“同层相同字符剪枝”，组合的去重条件是“限定起始下标”，子集的去重条件是“排序后跳过相同元素”。这些差异记熟了之后，你会发现回溯题根本不是靠背代码，而是靠理解“状态树长什么样”来解题。BM58 就是你把“状态树”这个概念建立起来的最佳起点。
