acwing170. 加成序列

题目

题解

path[0]=1,path[m]=n
其中path[1-m]递增，并且任意一个path[t]都可以由小于自身的两个数相加得到。

#include<iostream>
using namespace std;
const int N=110;
int path[N];
int n;

bool dfs(int u,int k){
    if(u==k)return path[u-1]==n;
    bool st[N]={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,k))return true;
        }
    }
    return false;
}
int main(){
    path[0]=1;
    while(cin>>n,n){
        int k=1;
        while(!dfs(1,k))k++;
        for(int i=0;i<k;i++)cout<<path[i]<<" ";
        puts("");
    }
    
    
    return 0;
}