恢复现场

本节学会什么

• 找出递归调用前被修改的全局状态
• 在递归返回后恢复所有被修改的状态
• 理解恢复现场与枚举答案正确性的关系

为什么需要它

《前进与回溯》用 enter/leave 观察了“调用前前进、返回后回溯”，但没有真正的状态需要维护。放苹果这类题要求每个分支相互独立：这一层选择的分苹果方案，不能影响下一个分支。只要递归前修改了变量，返回后就必须还原，否则后面的分支会带着错误的数据。放苹果是第一个需要同时恢复两个状态的完整例子。

最小可运行示例

把 m 个完全相同的苹果放进 n 个相同的盘子，允许空盘，问有多少种放法（顺序无关）。这是洛谷 P2386。

先看带输出的观察版：递归前进时记录每个盘子分到的苹果数，返回时恢复现场，cnt 累计合法方案：

#include <iostream>

int m, n;           // m 个苹果，n 个盘子
int a[100];         // a[i]：第 i 个盘子分到的苹果数
int cnt = 0;        // 合法方案数

void take(int dep, int num) {
    m -= num;
    a[dep] = num;
}

void put_back(int dep) {
    m += a[dep];
    a[dep] = 0;
}

void dfs(int dep) {
    if (dep == n) {
        take(dep, m);                    // 最后一个盘子拿走全部剩余苹果
        if (a[dep] >= a[dep - 1]) {      // 分配数不下降，避免重复方案
            cnt += 1;
            for (int i = 1; i <= n; i += 1) {
                std::cout << a[i] << ' ';
            }
            std::cout << '\n';
        }
        put_back(dep);
        return;
    }
    for (int i = a[dep - 1]; i <= m; i += 1) {   // 不小于上一个盘子
        take(dep, i);
        dfs(dep + 1);
        put_back(dep);
    }
}

int main() {
    std::cin >> m >> n;
    dfs(1);
    std::cout << cnt << '\n';
    return 0;
}

输入 4 2，输出 0 4、1 3、2 2 和计数 3。注意 take 修改了两个全局状态：m 减少、a[dep] 记下选择；put_back 把两个状态都还原。dfs 里的每一次 take 都对应一次 put_back，这就是“前进时修改、返回时恢复”的完整落实。

打开交互演示（放苹果 · 恢复现场）：逐步观察每一行代码如何修改与恢复现场，可随时更改苹果和盘子数量。

为什么需要 a[dep] >= a[dep - 1]：苹果相同、盘子相同，1 3 和 3 1 是同一种放法。让每个盘子的分配数单调不减，每个方案就只被枚举一次。

提交版把观察用的打印去掉，只在边界处计数：

#include <iostream>

int m, n;
int a[100];
int cnt = 0;

void dfs(int dep) {
    if (dep == n) {
        if (m >= a[dep - 1]) {   // 最后一个盘子拿走剩余全部苹果
            cnt += 1;
        }
        return;
    }
    for (int i = a[dep - 1]; i <= m; i += 1) {
        a[dep] = i;
        m -= i;
        dfs(dep + 1);
        m += i;                  // 恢复剩余苹果数
    }
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> m >> n;
        cnt = 0;
        dfs(1);
        std::cout << cnt << '\n';
    }
    return 0;
}

这个版本没有 take/put_back，恢复语句直接写在递归调用后面：m -= i 与 m += i 成对出现。a[dep] 没有显式恢复——它在下一次循环立刻被重新写入，读到的永远是新值。

关键过程与易错点

• 递归前修改了几个全局状态，返回前就要恢复几个。这里 m 和 a[dep] 是成对修改的。
• m 必须恢复。若删掉 m += i，下一个分支会带着减少过的苹果数，边界判断和枚举范围全部错误。
• a[dep] 可以不显式恢复，因为它总是在被读取前重新写入。要不要恢复，取决于“会不会读到旧值”。
• 边界处（最后一个盘子）依然要检查单调条件，否则会数出重复方案。
• 去重靠单调条件而不是比较历史方案：a[dep] >= a[dep - 1] 让分配数不下降。
• 观察版的输出语句放在边界处，因为那时一个完整方案刚形成；提交前删掉即可。

动手检查

对 m = 4, n = 2 手写全部方案，再运行观察版核对是否为 0 4、1 3、2 2 三种。

删掉提交版里的 m += i;，用样例重新运行，观察计数为什么变大。

把 m 改成函数参数（dfs(dep, left)），比较“参数传递”与“全局变量 + 恢复”两种写法：参数版里每个分支自带一份 left，返回时天然恢复，不再需要 m += i。

立即练习