170. 加成序列 题解

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int n, path[N];
 
bool dfs(int u, int depth)  // u表示当前层数, depth表示最大的深度
{
    if (u == depth) return path[u - 1] == n;  //如果已经到达最大深度，比较数值
    
    bool vis[N] = {0};  // 通过 bool数组排除等效冗余,且每进入一层都会初始化为0
    for (int i = u - 1; i >= 0; i--)
        for (int j = i; j >= 0; j--)  // 按组合数的方式枚举
        {
            int s = path[i] + path[j];
            if (s > n || s <= path[u - 1] || vis[s])    continue;  // path一定是递增的
            vis[s] = true;
            path[u] = s;  // 记录路径
            if (dfs(u + 1, depth))  return true;
        }
    return false;
}

int main()
{
    while (cin >> n, n)
    {
        path[0] = 1;
        int depth = 1;  // 表示深搜的最大深度，超过则返回
        while (!dfs(1, depth)) depth++;  //从第1层开始，最大层是第depth层, 如果找不到答案，慢慢增加深度

        for (int i = 0; i < depth; i++) cout << path[i] << ' ';
        cout << endl;
    }
    return 0;
}