18. 字符串的排列与组合：全排列的递归实现，字符串的所有子集

好，咱们今天聊点硬核的——字符串的排列与组合。这两个问题，说白了就是「把字符重新排序」和「挑出一些字符来」。听起来简单？嗯，但递归实现里藏着不少坑。我当年第一次写全排列时，调试到怀疑人生。

18.1 全排列的递归实现

全排列，就是把字符串里的所有字符，按所有可能的顺序排一遍。比如 "abc"，排列出来就是 abc、acb、bac、bca、cab、cba，一共 6 种。

递归的思路其实很朴素：固定第一个字符，然后对剩下的字符做全排列。你想想看，这不就是「分而治之」吗？

我习惯用交换法来实现。什么意思呢？就是让每个字符都有机会站到第一个位置，然后递归处理后面的部分。

#include <stdio.h>
#include <string.h>

// 交换两个字符
void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

// 全排列递归函数
void permute(char *str, int left, int right) {
    if (left == right) {
        // 已经排到最后一个字符，输出结果
        printf("%s\n", str);
        return;
    }

    for (int i = left; i <= right; i++) {
        // 固定第 left 个位置为 str[i]
        swap(&str[left], &str[i]);
        // 递归处理剩下的字符
        permute(str, left + 1, right);
        // 回溯：恢复原来的顺序
        swap(&str[left], &str[i]);
    }
}

int main() {
    char str[] = "abc";
    int n = strlen(str);
    printf("字符串 \"%s\" 的全排列：\n", str);
    permute(str, 0, n - 1);
    return 0;
}

运行结果：

abc
acb
bac
bca
cba
cab

注意那个回溯的 swap。我曾经漏掉这一步，结果递归回来时字符串顺序全乱了，输出一堆重复的排列。嗯，回溯是递归的灵魂，忘了它你就等着哭吧。

18.2 字符串的所有子集

子集问题，说白了就是「选或不选」。每个字符有两种状态：在子集里，或者不在。所以 n 个字符的字符串，一共有 2^n 个子集（包括空集）。

递归实现也很直观：从第一个字符开始，要么选它，要么不选它，然后继续处理下一个字符。

#include <stdio.h>
#include <string.h>

// 辅助数组，记录当前子集
char subset[100];

// 生成所有子集
void subsets(char *str, int index, int len, int pos) {
    // 输出当前子集
    printf("{");
    for (int i = 0; i < pos; i++) {
        printf("%c", subset[i]);
    }
    printf("}\n");

    // 从 index 开始，依次选择字符
    for (int i = index; i < len; i++) {
        // 选当前字符
        subset[pos] = str[i];
        // 递归处理后面的字符
        subsets(str, i + 1, len, pos + 1);
        // 回溯：其实这里不需要显式删除，因为下次会覆盖
    }
}

int main() {
    char str[] = "abc";
    int n = strlen(str);
    printf("字符串 \"%s\" 的所有子集：\n", str);
    subsets(str, 0, n, 0);
    return 0;
}

运行结果：

{}
{a}
{ab}
{abc}
{ac}
{b}
{bc}
{c}

注意看，这个顺序不是字典序，而是按「选字符的先后顺序」来的。如果你想要字典序，可以先对字符串排序，或者用另一种方法——位掩码法。

void subsets_bitmask(char *str) {
    int n = strlen(str);
    int total = 1 << n;  // 2^n

    for (int mask = 0; mask < total; mask++) {
        printf("{");
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                printf("%c", str[i]);
            }
        }
        printf("}\n");
    }
}

我个人更喜欢位掩码法，代码简洁，而且不用递归，性能也好。但递归法更容易理解「选或不选」这个核心思想。

18.3 知识体系图

下面这张图帮你理清本章的知识脉络：

18.4 避坑指南

我这些年写递归，踩过的坑比走过的路还多。给你列几个最常见的：

• 忘记回溯——交换法里，递归完一定要换回来。我曾经漏了这一步，结果排列结果全是错的。
• 递归终止条件写错——全排列是 left == right 时输出，子集是处理完所有字符时输出。别搞混了。
• 字符串长度别算错——strlen 返回的是字符个数，不包括 '\0'。但你的字符数组要留够空间。
• 重复字符没处理——如果字符串里有重复字符，不剪枝的话会输出大量重复排列。面试官看到会皱眉头的。

18.5 实战经验

我在做密码破解工具时，遇到过需要生成所有可能的密码组合。嗯，就是全排列的变种——每个位置可以选多个字符，而且可以重复。那叫「可重复排列」，用递归实现时，每次递归都从 0 开始遍历字符集，而不是从 left+1 开始。

还有一次，我在做数据脱敏工具，需要生成某个字段的所有可能取值子集。用位掩码法，一个 int 就能搞定 32 个字符的所有子集，性能杠杠的。

说白了，排列组合问题在面试里出现频率极高。不是因为实际工作中天天用，而是因为它能考察你对递归和回溯的理解深度。你想想看，能把递归写明白的人，写其他代码也不会差到哪去。

---

公众号:蓝海资料掘金营，微信deep3321