加成序列
迭代加深:每次设置一个深度,并且dfs,当前dfs的时候达到这个设置的深度时就返回。深度从1到n遍历,有合法方案就返回
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int path[N];
int n;//必须在全局定义,否则dfs中无法使用该变量
bool dfs(int u,int k){
if(u>k)return false;
if(path[u-1]==n)return true;
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(st[s]||s>n||s<=path[u-1])continue;
//s需要没有被用过,s不能大于最后一个数,s不能小于等于前面的数
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]<<' ';
cout<<endl;
}
return 0;
}