子集生成

许多看似复杂的问题都能通过“穷举所有可能”来解决——即暴力枚举。虽然乍看笨拙，却常常是最直接、最可靠的手段。实际开发里，BFS 搜索最短路径、回溯找解、组合枚举等都离不开这种思想。

2019年8月30日技术 , 数据结构与算法 1 分钟阅读

本文聚焦暴力枚举中的典型问题：给定集合生成全部子集（Power Set）。其他如排列、路径搜索将在后续再谈。

给定一个不含重复元素的数组 nums，输出它的所有子集，即 LeetCode 78 - Subsets。答案规模为 2^n，任何算法都至少需要线性时间输出这些结果。

以下三种常用方法可以覆盖大多数子集生成需求：增量构造法、递归回溯（位向量法）、位运算法（枚举二进制）。如果原数组包含重复元素，可在生成过程中去重，或先排序再跳过相同值，下文会给出提示。

从空集开始，每遍历一个元素就把当前结果集复制一份并追加该元素。最终得到的集合数正好翻倍。

以 [1,2,3] 为例：

初始结果：[]
处理 1：在现有集合的每个子集中追加 1，得到 []、[1]
处理 2：追加 2，得到 []、[1]、[2]、[1,2]
处理 3：同理可得 []、[1]、[2]、[1,2]、[3]、[1,3]、[2,3]、[1,2,3]

时间复杂度 O(n·2^n)，空间复杂度 O(2^n)。

vector<vector<int>> subsets(vector<int> &S) {
    vector<vector<int>> res(1);
    sort(S.begin(), S.end());
    for (int i = 0; i < S.size(); i++) {
        int size = res.size();
        for (int j = 0; j < size; j++) {
            res.push_back(res[j]);
            res.back().push_back(S[i]);
        }
    }
    return res;
}

若输入存在重复元素，可在遍历时记录本轮新增子集的范围，仅对新子集追加相同元素，避免重复结果。整个添加的顺序为：

[]
[1]
[2]
[1 2]
[3]
[1 3]
[2 3]
[1 2 3]

每个元素都有「选 / 不选」两种状态，可以模型化为一棵二叉决策树：左子树表示选择当前元素，右子树表示不选，叶子节点即为所有子集。状态树如下：

                        []
                   /          \
                  /            \
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

代码如下：

vector<vector<int>> subsets(vector<int> &S) {
    vector<vector<int>> res;
    vector<int> path;
    sort(S.begin(), S.end());
    genSubsets(S, 0, path, res);
    return res;
}
void genSubsets(vector<int> &S, int pos, vector<int> &path, vector<vector<int>> &res) {
    res.push_back(path);
    for (int i = pos; i < S.size(); i++) {
        if (i > pos && S[i] == S[i - 1]) continue; // 若有重复元素，跳过
        path.push_back(S[i]);
        genSubsets(S, i + 1, path, res);
        path.pop_back();
    }
}

整个添加的顺序为:

[]
[1]
[1 2]
[1 2 3]
[1 3]
[2]
[2 3]
[3]

集合中每个元素只有「选 / 不选」两种状态，与二进制位一一对应。将长度为 n 的集合映射为 0 ~ (1<<n)-1 的二进制数，即可枚举所有子集。下表展示了 [1,2,3] 的映射关系：

	1	2	3	Subset
0	0	0	0	[]
1	0	0	1	[3]
2	0	1	0	[2]
3	0	1	1	[2,3]
4	1	0	0	[1]
5	1	0	1	[1,3]
6	1	1	0	[1,2]
7	1	1	1	[1,2,3]

对应的代码如下：

vector<vector<int>> subsets(vector<int> &S) {
    vector<vector<int>> res;
    sort(S.begin(), S.end());
    int total = 1 << S.size();
    for (int mask = 0; mask < total; mask++) {
        vector<int> subset;
        for (int i = 0; i < S.size(); i++) {
            if ((mask >> i) & 1) {
                subset.push_back(S[i]);
            }
        }
        res.push_back(move(subset));
    }
    return res;
}

三种方法时间复杂度均为 O(n · 2^n)，差别主要在实现方式与常数因子；
增量构造适合迭代实现，回溯法便于剪枝或附加条件，位运算适合底层性能优化；
处理含重复元素的集合时，记得先排序并在生成过程中跳过重复值；
可扩展到相关问题：求固定长度子集、求满足约束的子集（在回溯时提前剪枝）、统计数量等。

暴力枚举并不意味着粗糙，只要设计好状态与剪枝策略，就能在 2^n 的搜索空间里快速找到答案。

概述

问题定义

方法一：增量构造

方法二：递归回溯（位向量法）

方法三：位运算枚举

小结