迭代加深

#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 3 * 1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int n;
int path[N];
bool dfs(int u,int depth) //u-当前层数，depth-能迭代的最大层数
{
    if(u > depth) return false;//如果超过最大层数，返回false
    if(path[u-1] == n) return true;
    //最后一层等于n找到合法解，返回true
    bool st[1100]={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] || st[s]) continue;
            //前两个数之和大于最后需要的数或者和比前一个数小或者已经访问过，则直接叉掉
            st[s] = true;
            path[u] = s;
            if(dfs(u+1,depth)) return true; //继续访问下一层，也就是搜索下一个该加到序列的数，直到搜到合法解
            st[s] = false; //回溯
        }
    }
    return false; //没找到，返回false
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    path[0] = 1;//赋初值
    while(cin>>n)
    {
        if(n==0) return 0;
        int depth = 1; 
        while(!dfs(1,depth)) depth++;//迭代加深，找最小长度的答案
        for(int i=0;i<depth;i++) cout<<path[i]<<' ';
        cout<<endl;
    }
    return 0;
}