递归枚举

本节学会什么

• 用递归枚举每个位置的选择
• 在边界处输出一组完整方案
• 用数组保存当前方案并正确回溯

为什么需要它

“每个数选或不选”“从若干数中选出若干个”“排列所有数字”都有许多方案。递归可以把第 pos 步要做的选择写清楚，再让下一层处理剩余位置。

最小可运行示例

输出 1 到 n 的所有选取方案：

#include <iostream>

int chosen[25];

void enumerate(int pos, int n) {
    if (pos > n) {
        for (int i = 1; i <= n; i += 1) {
            if (chosen[i]) {
                std::cout << i << ' ';
            }
        }
        std::cout << '\n';
        return;
    }

    chosen[pos] = 0;
    enumerate(pos + 1, n);
    chosen[pos] = 1;
    enumerate(pos + 1, n);
}

int main() {
    int n;
    std::cin >> n;
    enumerate(1, n);
    return 0;
}

每个位置有“不选”和“选”两个分支，所以总方案数是 2^n。当 pos > n 时，所有位置都已经决定，才能输出一组完整方案。

关键过程与易错点

• 先定义状态含义：这里 chosen[i] 为 1 表示选第 i 个数。
• 一个递归层要覆盖所有可能选择；漏一个分支就会漏方案。
• 每次递归都让 pos 加一，边界是 pos > n。
• 输出空集时会得到空行，这是“一个元素也不选”的正常方案；题目是否需要它由题意决定。
• n 增加一点，方案数会成倍增长。先确认数据范围，不能把 n = 30 当作小题。

动手检查

输入 n = 2，手写四种选法，再比对输出是否各出现一次。将输出改成 0/1 序列，检查每一位的选择是否正确。

把“选或不选”改为“当前位置填 0 或 1”，输出长度为 n 的所有二进制串。

立即练习