递归实现多重循环

一句话算法

递归实现多重循环，就是把“第几层循环”变成 DFS 的参数。

问题模型

有 n 个位置，每个位置都可以从 0, 1, ..., m - 1 中选择一个值，要求输出所有长度为 n 的序列。

如果 n = 3，可以写三层循环：

        
1
2
3
4

        for (int a = 0; a < m; ++a)
  for (int b = 0; b < m; ++b)
    for (int c = 0; c < m; ++c)
      ...
    

但当 n 是输入的一部分时，循环层数不固定，就需要用递归来生成这些循环。

核心直觉

每一层递归负责填写一个位置。

• dfs(1) 填第 1 个位置。
• dfs(2) 填第 2 个位置。
• …
• dfs(n + 1) 表示前 n 个位置都填完，可以输出答案。

所以递归不是神秘操作，它只是把固定层数的循环改成了“运行时决定层数”的循环。

算法步骤

1. 用数组 path 保存当前已经填好的序列。
2. 定义 dfs(dep)，表示现在要填写第 dep 个位置。
3. 如果 dep > n，说明一个完整序列已经形成，输出 path。
4. 否则枚举当前位置的每个可能值 x：
   • 令 path[dep] = x。
   • 递归调用 dfs(dep + 1)。

算法证明

关键不变量： 进入 dfs(dep) 时，path[1..dep-1] 已经确定，且它表示某个合法前缀。

1. 初始进入 dfs(1) 时，空前缀合法。
2. 在 dfs(dep) 中，枚举当前位置的所有可能值，所以每个合法前缀都会扩展出所有合法下一步。
3. 当 dep > n 时，前缀长度正好为 n，得到一个完整序列。
4. 每个位置的选择顺序唯一，所以同一个序列只会沿着唯一一条递归路径生成一次。

因此算法不重不漏地枚举了所有序列。

复杂度分析

一共有 $m^n$ 个序列，每个序列输出 $n$ 个数。

• 时间复杂度：$O(n \cdot m^n)$，如果不计输出代价，递归状态数是 $O(m^n)$。
• 空间复杂度：$O(n)$，用于递归栈和当前路径。

代码实现

        
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);
}
    

测试用例

输入：

2 3

输出：

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

应用分类详解

递归多重循环的本质是枚举“固定长度决策序列”。

一、每个位置独立选择

典型模式： 每个位置都有相同或相近的取值范围。

识别信号： 输出所有长度为 n 的方案、每个位置可选若干值。

核心建模： dep 表示正在决定的位置。

二、搜索树的基础模型

典型模式： 题目要求试遍所有选择路径。

识别信号： 所有方案、回溯、暴力枚举、状态空间。

核心建模： 每个递归节点是一段前缀，每条边代表追加一个选择。

经典例题

• 输出所有 01 串：把 m 固定为 2。
• 全排列：在多重循环基础上加 used 数组限制不能重复选。
• 组合枚举：在多重循环基础上加“下标递增”限制。

参考

• 本书相关章节：全排列、子集枚举