递归枚举

一句话理解

递归枚举是用递归把所有方案列出来。

为什么要学

子集、排列、组合搜索的底子。

讲解

对每个位置：选或不选，或选哪个数。递归参数记录“现在考虑到第几位、当前状态是什么”。

走到底就记录答案，然后回溯恢复现场。下一课专门讲回溯。

例子

void dfs(int i) {
    if (i == n) { /* 记录一种方案 */ return; }
    // 不选 i
    dfs(i + 1);
    // 选 i
    choose(i);
    dfs(i + 1);
    unchoose(i);
}

每个元素两条路，共 2^n 种子集。n 必须很小。

常见错误

• n=30 还 2^n 枚举。
• 选了却不回溯，后面的方案脏掉。