子集枚举

普通子集枚举是对每个元素决定“选”还是“不选”；固定集合的子集枚举是从 `sub = mask` 开始，每次用 `(sub - 1) & mask` 跳到下一个子集。

  • 子集
  • 枚举
  • DFS
  • 二进制
  • 状态压缩

一句话算法

普通子集枚举是对每个元素决定“选”还是“不选”；固定集合的子集枚举是从 sub = mask 开始，每次用 (sub - 1) & mask 跳到下一个子集。

问题模型

给定 n 个元素，输出它的所有子集。

例如 {1, 2, 3} 的子集有：

空集
1
2
3
1 2
1 3
2 3
1 2 3

子集不关心元素被选中的顺序，只关心哪些元素被选中。

在状态压缩问题中，还会遇到另一个常见模型：

给定一个已经确定的集合 mask，枚举它的所有子集 sub。

例如：

mask = 1101

它的非空子集是：

1101
1100
1001
1000
0101
0100
0001

这些 sub 都满足：

cpp 
        
1

        (sub & mask) == sub

核心直觉

每个元素只有两种状态：

  • 选。
  • 不选。

所以总方案数是：

2n 2^n

这件事可以用 DFS 表达，也可以用二进制数表达。

如果已经有一个集合 mask，那么子集 sub 的每一位都不能超出 mask。也就是说：

  • mask 的某一位是 0，sub 这一位必须是 0；
  • mask 的某一位是 1，sub 这一位可以是 0 或 1。

所以 sub 不是在 0..mask 中随便找，而是在 mask 允许的位置上做选择。

算法步骤

DFS 枚举

DFS 写法把当前已经选择的元素放在 path 中。

  1. 进入 dfs(dep, last) 时，当前 path[1..dep-1] 已经是一个子集，先输出它。
  2. 继续枚举下一个被选择的元素下标 i，要求 i > last。
  3. 选择 a[i] 后递归到下一层。

这种写法天然保证子集中的下标递增，因此不会重复。

二进制枚举

用一个整数 mask 表示一个子集：

  • 第 i 位是 1：选择第 i + 1 个元素。
  • 第 i 位是 0：不选择第 i + 1 个元素。

枚举 mask = 0..(1 << n) - 1，就枚举了所有子集。

固定集合的子集枚举

如果 A 表示一个集合，枚举它的所有非空子集可以写成：

cpp 
        
1
2
3

        for (int s = A; s; s = (s - 1) & A) {
    // s 是 A 的一个非空子集
}

如果也要枚举空集，可以在循环后单独处理 0，也可以写成：

cpp 
        
1
2
3
4

        for (int s = A;; s = (s - 1) & A) {
    // s 是 A 的一个子集，包含空集
    if (s == 0) break;
}

“和普通二进制枚举的区别”

for (mask = 0; mask < (1 << n); mask++) 枚举全集的所有子集。

for (s = A; s; s = (s - 1) & A) 枚举某个给定集合 A 的所有非空子集。

算法证明

DFS 写法

关键不变量： path 中的元素下标严格递增。

每次递归只选择 last 后面的元素，所以不变量始终成立。任意一个子集把下标按升序排列后，都会对应唯一一条 DFS 路径；DFS 又会在进入每个状态时输出当前集合。因此不重不漏。

二进制写法

每个元素的选择状态只有 0 和 1 两种。长度为 n 的二进制串和 n 个元素的子集一一对应：

mask↔{ai∣mask 的第 i 位为 1} mask \leftrightarrow \{a_i \mid mask \text{ 的第 } i \text{ 位为 } 1\}

枚举所有 mask 就等价于枚举所有二进制选择状态，因此能枚举全部子集。

固定集合子集枚举

核心直觉： s - 1 负责找下一个更小状态，& A 负责把不属于 A 的位清掉。

设当前状态为 s。执行 s - 1 时，二进制会发生这样的变化：

s     = 前缀 1 00...0
s - 1 = 前缀 0 11...1

也就是：最低位的 1 被清掉，它右边的位都变成 1。

但是这些新变成 1 的位，不一定属于原集合 A。所以再做：

cpp 
        
1

        (s - 1) & A

就只保留 A 中允许出现的位。

整个过程有两个关键点：

  1. 每次更新后，新的 s 一定仍然是 A 的子集。
  2. 每次更新后，s 严格变小，所以不会重复。

从 A 自己开始，不断跳到下一个更小的子集，直到 0 停止，因此能枚举出所有非空子集。

复杂度分析

一共有 2n2^n 个子集。

  • 时间复杂度：O(n⋅2n)O(n \cdot 2^n)，因为输出或检查每个子集时最多扫描 n 个元素。
  • 空间复杂度：
    • DFS 写法：O(n)O(n)。
    • 二进制写法：O(1)O(1) 额外空间，不计输入数组。

如果只枚举某个集合 mask 的子集，设 mask 中有 kk 个 1，则：

  • 非空子集数量：2k−12^k-1。
  • 时间复杂度：O(2k)O(2^k)。
  • 空间复杂度：O(1)O(1)，不计输出。

如果对所有 mask 都枚举它的所有子集：

cpp 
        
1
2
3
4
5

        for (int mask = 0; mask < (1 << n); ++mask) {
    for (int sub = mask; sub; sub = (sub - 1) & mask) {
        // sub
    }
}

总复杂度是 O(3n)O(3^n)。因为每一位有三种状态：

  • 不在 mask 中；
  • 在 mask 中，但不在 sub 中；
  • 在 mask 中，也在 sub 中。

代码实现

DFS 子集枚举

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 30 + 5;

int n;
int a[maxn], path[maxn];

// 枚举所有子集。
// 每次进入 dfs 都输出当前已经选择的元素。
void dfs(int dep, int last) {
    for (int i = 1; i < dep; ++i) {
        cout << path[i] << (i + 1 == dep ? '\n' : ' ');
    }
    if (dep == 1) cout << "\n";  // 空集

    for (int i = last + 1; i <= n; ++i) {
        path[dep] = a[i];
        dfs(dep + 1, i);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    dfs(1, 0);
    return 0;
}

二进制子集枚举

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 30 + 5;

int n;
int a[maxn];

// 用二进制状态枚举所有子集。
// mask 的第 i 位为 1，表示选择 a[i + 1]。
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int mask = 0; mask < (1 << n); ++mask) {
        bool first = true;
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                if (!first) cout << ' ';
                first = false;
                cout << a[i + 1];
            }
        }
        cout << '\n';
    }
    return 0;
}

固定集合的子集枚举

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

        #include <bits/stdc++.h>
using namespace std;

// 返回 mask 的所有非空子集。
// 这里的子集指二进制意义上的子掩码：sub 的 1 只能出现在 mask 为 1 的位置。
vector<int> non_empty_submasks(int mask) {
    vector<int> res;
    for (int sub = mask; sub; sub = (sub - 1) & mask) {
        res.push_back(sub);
    }
    return res;
}

void print_bits(int x, int n) {
    for (int i = n - 1; i >= 0; --i) {
        cout << ((x >> i) & 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, mask;
    cin >> n >> mask;

    for (int sub : non_empty_submasks(mask)) {
        cout << sub << ' ';
        print_bits(sub, n);
        cout << '\n';
    }

    // 如果需要枚举空集，在循环后单独处理 0 即可。
    return 0;
}

测试用例

输入：

3
1 2 3

一种可能输出：


1
1 2
1 2 3
1 3
2
2 3
3

第一行为空集。不同枚举方式输出顺序可以不同，但子集集合应该相同。

固定集合子集枚举示例：

输入：

4 13

这里 13 的二进制是 1101。输出：

13 1101
12 1100
9 1001
8 1000
5 0101
4 0100
1 0001

应用分类详解

子集枚举的本质是枚举“每个元素是否被选中”的所有状态。

一、小规模集合暴力

典型模式： n 较小，要求从所有元素中选任意多个。

识别信号： 任选子集、所有集合、n <= 20 左右。

核心建模： 一个 mask 或一条 DFS 路径表示一个选择集合。

应用场景 经典题目 核心思路
子集输出 leetcodecn-78 直接枚举所有选择状态
小规模最优选择 状态压缩暴力 枚举集合后计算代价
朴素验证 luogu-P14360 小数据下枚举所有木棍集合并检查是否合法

二、状态压缩 DP 的入口

典型模式： 集合状态要参与转移。

识别信号： 已选集合、剩余集合、用二进制表示状态。

核心建模： mask 表示当前已经选择的元素集合。

应用场景 经典题目 核心思路
状压 DP 旅行商小规模模型 mask 记录已访问点
子集转移 SOS DP 入门 在集合的子集之间转移

三、枚举某个集合的子集

典型模式： 已经有一个集合 mask，需要枚举它的所有子集。

识别信号： 枚举 s 满足 s 是 mask 的子集，或转移中出现 sub ⊆ mask。

核心建模： 使用 sub = (sub - 1) & mask 枚举。

应用场景 经典题目 核心思路
子集 DP 集合划分 枚举当前集合的一个子集
容斥计算 小规模集合统计 遍历所有包含关系
SOS DP 暴力入口 SOS DP 对每个 mask 枚举 sub ⊆ mask，再优化成 SOS DP

“P14360 brute 代码对应哪一种”

luogu-P14360 的朴素代码是枚举所有 mask，即枚举所有木棍选择集合。

如果某个状态转移需要“在当前集合 mask 中再选一个子集 sub”，才使用 (sub - 1) & mask。

经典例题

  • leetcodecn-78 子集：标准子集枚举。
  • leetcodecn-90 子集 II：含重复元素时需要去重。
  • luogu-P1433 吃奶酪：状态压缩 DP 的典型入口。
  • luogu-P14360 多边形：朴素做法枚举所有木棍子集，适合用来理解 mask 表示一个选择集合。
  • SOS DP：暴力写法需要对每个 mask 枚举 sub ⊆ mask，是固定集合子集枚举最常见的入口。

参考