22、递归与字符串：字符串全排列（去重版本）
字符串全排列，是递归里一个经典得不能再经典的题目。很多面试官喜欢拿它来考察你对递归的理解深度。今天我们就来聊聊它的去重版本——说白了，就是给你一个字符串，输出它所有不重复的排列方式。
我记得刚入行那会儿，第一次写全排列，写出来的代码能跑，但一遇到重复字符就崩。嗯，那时候还没意识到去重的重要性。后来在项目中处理用户输入的关键词组合时，才真正体会到「去重」这两个字的分量。
什么是全排列？
先简单回顾一下。全排列，就是把一个字符串里的所有字符，按照不同的顺序重新组合。比如字符串 "abc"，它的全排列有 6 种：
abc acb bac bca cab cba但如果字符串里有重复字符呢？比如 "aab"，如果还用老方法，你会得到：
aab aba aab aba baa baa看到没？"aab" 和 "aba" 各出现了两次。这显然不是我们想要的。去重版本要做的就是：只输出不重复的排列。
核心思路：交换法 + 剪枝
全排列的递归实现，我个人习惯用「交换法」。思路是这样的：
- 把字符串看作一个字符数组。
- 固定第一个位置，依次把每个字符换到这个位置。
- 对剩下的子串递归做全排列。
- 递归回来再换回去（回溯）。
去重怎么加？关键就在「固定第一个位置」这一步。如果某个字符之前已经在这个位置出现过了，那这次就不用再换了。说白了，就是用一个集合记录一下当前位置已经放过哪些字符。
核心原则：在每一层递归中，只把「第一次出现」的字符换到当前位置。重复的跳过。
代码实现
下面是我写的一个去重版本。代码不长，但每一行都有它的道理。
#include <stdio.h>
#include <string.h>
// 交换两个字符
void swap(char *a, char *b) {
char tmp = *a;
*a = *b;
*b = tmp;
}
// 判断在 [start, end) 范围内，字符 c 是否出现过
int isDuplicate(char str[], int start, int end) {
for (int i = start; i < end; i++) {
if (str[i] == str[end]) {
return 1; // 出现过，重复
}
}
return 0;
}
// 递归生成全排列（去重）
void permute(char str[], int index, int len) {
if (index == len) {
printf("%s\n", str);
return;
}
for (int i = index; i < len; i++) {
// 去重：如果 str[i] 在 [index, i) 中出现过，跳过
if (isDuplicate(str, index, i)) {
continue;
}
swap(&str[index], &str[i]);
permute(str, index + 1, len);
swap(&str[index], &str[i]); // 回溯
}
}
int main() {
char str[] = "aab";
int len = strlen(str);
permute(str, 0, len);
return 0;
}运行结果：
aab
aba
baa完美去重。
图解递归过程
光看代码可能还不够直观。我画了一张流程图，帮你理清递归的调用过程。以 "aab" 为例：
从图中可以清楚看到：当 index=0 时，i=1 对应的字符是 'a'，而 'a' 已经在 index=0 的位置出现过了（i=0 时换的就是 'a'），所以直接跳过。这样就避免了重复排列的产生。
去重的关键：isDuplicate 函数
这个函数虽然只有几行，但它是整个去重逻辑的核心。它的作用是在 [start, end) 范围内查找字符 str[end] 是否已经出现过。如果出现过，说明当前字符之前已经被换到 start 位置处理过了，这次再换就会产生重复。
小技巧：你也可以用一个哈希表（比如 bool visited[256]）来加速判断，尤其是当字符串很长时。不过对于一般面试题，线性查找就够用了。
复杂度分析
| 指标 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n! × n) | 最坏情况下生成 n! 个排列，每个排列需要 O(n) 时间输出 |
| 空间复杂度 | O(n) | 递归栈深度为 n，加上字符串本身 |
你可能会问：去重之后复杂度会不会降低？其实不会。因为最坏情况（所有字符都不同）下，排列数还是 n!。去重只是避免了重复的递归分支，但并没有改变最坏情况的上界。
避坑指南
我曾经在项目里用全排列处理一批商品标签的组合，结果因为没去重，生成了大量重复数据，导致后续的推荐算法跑出来一堆冗余结果。排查了半天才发现是去重逻辑漏了。
这里有几个常见的坑，你写代码的时候注意一下：
- 忘记回溯：交换之后一定要换回来，否则会影响后续的排列。这是新手最容易犯的错误。
- 去重范围搞错：isDuplicate 的查找范围是
[index, i)，不是[0, i)。因为我们要判断的是「当前位置」之前是否出现过这个字符，而不是整个字符串。 - 输入字符串未排序：去重版本不要求输入字符串有序，但如果你用另一种方法（比如标记法），排序可以帮你更方便地跳过重复字符。
注意：如果字符串很长（比如超过 10 个字符），全排列的数量会爆炸式增长。n=12 时就有 4.79 亿种排列，你的程序可能会跑很久。实际项目中要谨慎使用。
另一种思路：标记法
除了交换法，还有一种常见的实现方式是用一个额外的数组来标记哪些字符已经被使用过。这种方法的好处是不需要修改原字符串，但需要额外的空间。
void permuteWithFlag(char str[], int used[], char result[], int depth, int len) {
if (depth == len) {
printf("%s\n", result);
return;
}
for (int i = 0; i < len; i++) {
// 去重：如果当前字符和前一个相同，且前一个没被用过，跳过
if (used[i] || (i > 0 && str[i] == str[i-1] && !used[i-1])) {
continue;
}
used[i] = 1;
result[depth] = str[i];
permuteWithFlag(str, used, result, depth + 1, len);
used[i] = 0;
}
}这种写法要求输入字符串是排序好的。我个人更习惯交换法，因为不需要额外数组，代码也更简洁。不过两种方法都能用，看你的个人喜好。
小结
字符串全排列的去重版本，说白了就是在递归过程中加一道「剪枝」逻辑。每次固定一个位置之前，先看看这个字符之前有没有出现过。有就跳过，没有就继续。
这个思路不光适用于全排列，很多回溯问题（比如组合、子集）的去重都可以用类似的方法。你想想看，是不是这个道理？
好了，这一节的内容就到这里。代码不多，但背后的递归思想值得反复琢磨。下次遇到类似的去重问题，你应该知道怎么下手了。
公众号:蓝海资料掘金营，微信deep3321