12、递归与回溯：子集生成

说到递归，很多人第一反应是阶乘、斐波那契。但说实话，这些例子太「教科书」了。真正让我觉得递归有魅力的，是子集生成——也就是求一个集合的所有子集，也叫幂集。

我记得刚入行那会儿，有个需求是让用户勾选一组配置项，然后系统自动生成所有可能的组合。我当时第一反应是写多层循环，结果发现元素个数一变，代码就得重写。后来才意识到，这其实就是个递归回溯的问题。

什么是幂集？

先明确概念。给定一个集合，比如 {1, 2, 3}，它的所有子集包括：

• 空集：{}
• 单元素：{1}、{2}、{3}
• 双元素：{1,2}、{1,3}、{2,3}
• 三元素：{1,2,3}

一共 2³ = 8 个。没错，n 个元素的集合，幂集大小就是 2ⁿ。这个指数增长的特性，你心里要有数——n 到 20 左右还能跑，再大就吃力了。

核心思路：选或不选

子集生成的核心思想其实就一句话：每个元素要么选，要么不选。

你想想看，对于集合中的第一个元素，你有两种选择：

• 选它，然后递归处理剩下的元素
• 不选它，然后递归处理剩下的元素

这就是一个典型的二叉树递归结构。每个节点分两支，深度为 n，叶子节点就是最终的一个子集。

代码实现：递归版

先看最直观的写法。我用一个数组 track 来记录当前已经选中的元素，递归函数负责决策第 start 个元素。

#include <stdio.h>

void generateSubsets(int arr[], int n, int start, int track[], int trackSize) {
    // 打印当前子集
    printf("{ ");
    for (int i = 0; i < trackSize; i++) {
        printf("%d ", track[i]);
    }
    printf("}\n");

    // 从 start 开始，尝试选择后面的元素
    for (int i = start; i < n; i++) {
        // 做选择：把 arr[i] 加入当前子集
        track[trackSize] = arr[i];
        // 递归：决策下一个元素
        generateSubsets(arr, n, i + 1, track, trackSize + 1);
        // 回溯：撤销选择（这里其实不用显式操作，因为 trackSize 没变）
        // 但逻辑上，arr[i] 已经被「移除」了
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int track[100]; // 足够大
    generateSubsets(arr, n, 0, track, 0);
    return 0;
}

运行结果：

{ }
{ 1 }
{ 1 2 }
{ 1 2 3 }
{ 1 3 }
{ 2 }
{ 2 3 }
{ 3 }

嗯，注意看输出顺序。这不是乱序的，而是按照「字典序」生成的。为什么？因为每次递归都是从当前元素的下一个开始尝试，所以天然有序。

回溯的本质

刚才的代码里，我提到「回溯」这个词。说白了，回溯就是「撤销上一步的选择」。在这个例子中，我们并没有显式地删除 track 中的元素，因为每次递归调用时传的是 trackSize + 1，下一层递归返回后，trackSize 还是原来的值，相当于自动「回退」了。

但如果你用动态数组或者链表来存储子集，就需要手动 pop 了。我习惯这样写：

void backtrack(int arr[], int n, int start, int track[], int trackSize) {
    // 输出当前子集
    for (int i = 0; i < trackSize; i++) {
        printf("%d ", track[i]);
    }
    printf("\n");

    for (int i = start; i < n; i++) {
        track[trackSize] = arr[i];          // 做选择
        backtrack(arr, n, i + 1, track, trackSize + 1); // 递归
        // 回溯：trackSize 不变，相当于撤销了选择
    }
}

你看，回溯的「撤销」操作，有时候是隐式的。理解这一点很重要——回溯不是一定要写 pop 代码，而是逻辑上要回到决策前的状态。

另一种思路：位运算

递归回溯虽然直观，但如果你追求极致性能，或者 n 比较小（比如 n ≤ 20），位运算是更好的选择。

思路很简单：用一个整数的二进制位来表示每个元素选或不选。比如 n=3 时，0b000 表示空集，0b001 表示 {1}，0b101 表示 {1,3}，以此类推。

void generateByBit(int arr[], int n) {
    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("%d ", arr[i]);
            }
        }
        printf("}\n");
    }
}

这段代码简洁到令人发指。没有递归，没有回溯，一个循环搞定。但代价是什么？

• 只能处理 n ≤ 31（int 的位数限制，如果用 long long 可以到 63）
• 输出顺序是固定的（按二进制顺序）
• 无法在生成过程中做剪枝

所以我的建议是：如果 n 小且不需要剪枝，用位运算；如果 n 大或需要灵活控制，用递归回溯。

避坑指南

我曾经在项目里犯过一个低级错误：递归函数里用了全局变量来存子集，结果多个递归分支互相干扰。嗯，那会儿 debug 到凌晨两点才找到原因。

所以给你几个建议：

1. 递归函数尽量用参数传递状态，不要依赖全局变量。除非你非常清楚自己在做什么。
2. 注意递归深度。n=100 时递归深度就是 100，虽然 C 的栈一般够用，但如果你在递归里分配了大数组，栈溢出是分分钟的事。
3. 输出格式要统一。我习惯每个子集占一行，元素之间用空格分隔，空集输出空行或 { }。团队协作时，格式不一致会让人抓狂。

知识体系图

下面这张图帮你理清子集生成的几种思路和它们之间的关系：

实战建议

如果你刚开始学递归回溯，我建议你：

1. 先手写递归树。拿 n=3 的集合，把递归调用过程画一遍。每个节点代表一次函数调用，分支代表选或不选。画完你就懂了。
2. 从打印所有子集开始，不要一上来就想着剪枝优化。先把基础跑通。
3. 对比递归版和位运算版的输出。你会发现顺序不同，但内容一样。这能帮你理解两种思路的本质区别。

子集生成是递归回溯的「Hello World」。搞懂了它，后面再学全排列、组合、N皇后等问题，你会发现套路都差不多——做选择、递归、撤销选择。嗯，就这么简单。

---

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