python/TangDou/AcWing/DieDaiJiaShen/170_2.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 110;

// 利用a[u]=a[u-1]+?进行构建的性质进行优化

int n;     // 终点值n
int a[N];  // 填充的每个数字，路径
int depth; // 最小长度上限

// u:当前枚举到的位置
bool dfs(int u) {
    // 如果走完最后一个位置，来到了一个尾巴哨兵面前，此时，需要检查刚刚最后填入的a[u-1]是不是等于数字n,是则找到了答案，不是，则没有找到答案
    if (u == depth + 1) return a[u - 1] == n;

    for (int j = u - 1; j; j--) { // 前序填充数字中，任意两个数的和，可以重复使用同一个数字
        int s = a[u - 1] + a[j];  // 两个数的和,这是一个可能要填充到u位置上的解

        // 可行性剪枝
        // a数组必然是一个单调上升的序列，小于等于上一个位置的数字，都是不可能的分支

        // 如果本次枚举的数字比前一个还小的话，那么肯定不是解。
        if (s > n) continue; // 超过上界的肯定不对

        a[u] = s; // 将s放入路径中
        // 在放完u之后，走到u+1的位置，那么这条路径是不是合法，不再依赖于自己，而是依赖于u+1这步的探测结果
        if (dfs(u + 1)) return true;
    }

    // 如果所有组合都尝试了一遍，依然不可以找到true的答案，那么本路径无效
    return false;
}

int main() {
    // 题目要求:第1个数字是1,最后一个是n
    a[1] = 1;

    while (cin >> n, n) { // 多组测试数据，输入为0时停止,n是指序列的终止值
        depth = 1;        // 深度从1开始
        // 迭代加深
        while (!dfs(2)) depth++; // 从第2个位置开始搜索，不断放宽depth
        // 输出搜索路径
        for (int i = 1; i <= depth; i++) printf("%d ", a[i]);
        puts("");
    }
    return 0;
}