AcWing 170. 加成序列[曾用名：加法链]

题目传送门

一、题目解析

二、实现代码

#include 

using namespace std;
const int N = 110;

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

// 迭代加深
// u:当前枚举到的深度
// depth:规定的深度上限
bool dfs(int u) {
    //到达指定深度，那么填充的最后一个数字是不是想要的数字n呢？
    if (u == depth) return path[u - 1] == n;

    //判重数组,在函数内声明需要初始化
    bool st[N] = {false};
    //剪枝，想要填充u这个位置，那么倒序(从大到小)去尝试，这样更快
    //注： i>=0 可以写成 ~i ，表示 i!=-1,从大到小循环，其实 i!=-1就是i>=0,这样写更简单
    for (int i = u - 1; ~i; i--)
        for (int j = i; ~j; j--) {     //区间内任意两个数的和，可以重复
            int s = path[i] + path[j]; //两个数的和,这是一个可能要填充到u位置上的解，这个可不可以填充呢？

            //因为是从大到小枚举，如果出现s <= path[u - 1]，那么后面的s也必定 <= path[u - 1]。

            //注意：这里必须是保证倒序才能用这个逻辑，否则不可以使用
            if (s <= path[u - 1]) return false;

            // 1、s > n 大于目标值，此路径无意义
            // 2、st[s]本轮搜索过这个和了，不用再次搜索后续递归树
            if (s <= n && !st[s]) {
                st[s] = true; //标识本轮枚举两个数字的和时已使用过，注意这里不是回溯
                path[u] = s;  //将s放入路径中
                //在放完u之后，走到u+1的位置，那么这条路径是不是合法，不再依赖于自己，而是依赖于u+1这步的探测结果
                if (dfs(u + 1)) return true;
            }
        }
    //如果所有组合都尝试了一遍，依然不可以找到true的答案，那么本路径无效
    return false;
}

int main() {
    // 1是初始值，题目要求第1个数字必须是1,最后一个是n
    path[0] = 1;

    while (cin >> n, n) { //多组测试数据，输入为0时停止,n是指序列的终止值
        depth = 1;        //深度从1开始，因为1≤n≤100
        //下面应该是迭代加深的套路
        while (!dfs(1)) depth++;

        //输出搜索的路径
        for (int i = 0; i < depth; i++) cout << path[i] << ' ';
        cout << endl;
    }
    return 0;
}

总结：
由于是一层一层搜索的，因此保证了第一次搜索到结果就是答案，感觉是集成了宽搜和深搜的优点.