我的算法书 - 01 序列枚举

一句话算法

01 序列枚举就是每个位置只在 0 和 1 中选一个，本质是对布尔格（Boolean Lattice）的深度优先遍历。

问题模型

输入一个正整数 n，输出所有长度为 n 的 01 序列。

例如 n = 3：

“离散数学视角”

每个长度为 $n$ 的 01 序列对应全集包含 $n$ 个元素的一个子集（1 表示选取，0 表示不选取）。因此 01 序列枚举本质是对布尔格（Boolean Lattice） $\mathcal{B}_n = (\{0,1\}^n, \subseteq)$ 的 DFS 遍历，也就是幂集（Power Set）的构造过程。

核心直觉

每个位置有两个选择，所以总方案数是：

2^n

如果 n 固定为 3，可以写三层循环；但 n 是输入时，循环层数不固定，需要用递归实现。

这正是“递归实现多重循环”的特例：把 m 设为 2。

算法步骤

用 path[dep] 保存当前第 dep 个位置的值。
定义 dfs(dep) 表示正在填写第 dep 个位置。
如果 dep > n，输出一个完整序列。
否则枚举 x = 0, 1：
- path[dep] = x。
- 递归 dfs(dep + 1)。

算法证明

关键不变量： 进入 dfs(dep) 时，前 dep-1 个位置已经确定。

每一层都枚举当前位置的两个可能值，因此每个长度为 n 的 01 序列都能按它的每一位选择走出唯一递归路径。到达 dep > n 时输出完整序列，所以算法不重不漏。

复杂度分析

时间复杂度： $O(n \cdot 2^n)$ ，因为共有 $2^n$ 个序列，每个输出 n 位。
空间复杂度： $O(n)$ 。

代码实现

下面模板是通用多重循环枚举。输入 n 2 时，它输出的就是长度为 n 的 01 序列。

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

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

// 递归实现 n 层循环，每层都从 [0, m) 中选择一个值。
// emit(path) 会收到一个长度为 n 的完整序列。
template <class Emit>
void enumerate_dynamic_loop(int n, int m, const Emit& emit) {
    if (n < 0 || m < 0) return;

    vector<int> path(n, 0);

    auto dfs = [&](auto&& self, int dep) -> void {
        if (dep == n) {
            emit(path);
            return;
        }

        for (int x = 0; x < m; ++x) {
            path[dep] = x;
            self(self, dep + 1);
        }
    };

    dfs(dfs, 0);
}

测试用例

输入：

3 2

输出：

应用分类详解

01 序列的本质是“对 $n$ 个二选项进行分支决策”。随着约束与数据规模的变化，可以衍生出不同的求解模式：

一、基础 0/1 决策（子集选择）

典型模式： 每个元素仅有“选 / 不选”两种状态。 识别信号： 集合子集、开关状态、组合优化（ $n \le 20$ ）。 核心建模： 在 dep > n 终止时，遍历状态数组或直接维护累计状态值（如和、积）。

应用场景	经典题目	核心思路
选/不选综合属性优化	P2036 PERKET	跑 01 DFS，叶节点计算酸度积与苦味和的绝对差，需排除全 0 特例

二、带约束的 0/1 分支与剪枝

典型模式： 在 01 树生成过程中加入约束条件。 识别信号： 指定选择元素个数 $k$ 、限制总体容量。 核心建模： 记录已选元素个数 cnt。进入分支前检查 cnt + (n - dep + 1) < k，若成立则直接回溯（可行性剪枝）。

应用场景	经典题目	核心思路
固定选择个数	P1157 组合的输出	限制选中 `1` 的数量恰好为 $k$ ，配合剪枝将 $O(2^n)$ 优化到 $O(inom{n}{k})$

三、状态空间扩展（从 0/1 到全排列）

典型模式： 每个位置的分支数从 2 扩展到 $n$ 。 识别信号： 置换、元素互异性、字典序全排列。 核心建模： 循环变为 for (int i = 1; i <= n; ++i)，配合 vis 数组标记与回溯。

应用场景	经典题目	核心思路
置换群按字典序遍历	P1706 全排列问题	每次选择未使用的数字，递归后恢复 `vis` 现场

四、大范围 0/1 枚举（折半搜索 / Meet-in-the-Middle）

典型模式： $n \approx 40$ ，直接跑 $O(2^n)$ 会 TLE。 识别信号： $n \le 40$ 、选/不选决策、组合方案数统计。 核心建模： 将 $n$ 拆为前 $n/2$ 与后 $n/2$ ，分别跑 01 DFS 各得到 $2^{n/2}$ 种状态。对后半数组排序，遍历前半数组时用二分查找（std::upper_bound）匹配合法组合。

应用场景	经典题目	核心思路
大规模二选一方案计数	P4799 世界冰球锦标赛	前后各跑 $2^{20}$ DFS，得到数组 $A$ 与 $B$ ，对 $B$ 排序后配合二分统计 $A_i + B_j \le M$

经典例题

按“基础落地 -> 约束剪枝 -> 结构扩展 -> 折半跃迁”推荐以下练习：

P2036 [COCI 2008/2009 #2] PERKET：01 分支入门题。DFS 统计酸度和与苦味积，注意排除全不选的情况。
P1157 组合的输出：在 01 树上统计选中 1 的个数为 $k$ 的路径，引入可行性剪枝。
P1706 全排列问题：分支数从 2 扩展到 $n$ ，加入 vis 数组维护元素不重复使用。
P4799 [CEOI2015 Day2] 世界冰球锦标赛： $N \le 40$ 的 01 枚举高级应用，使用折半搜索（Meet-in-the-Middle）与二分查找拆分状态空间。

参考

本书相关章节：递归实现多重循环、子集枚举