首先，在这道题的搜索框架中，在对每一位进行枚举时，复杂度为\(O(n^2)\)，但是可知最优解序列的长度不会太长。

其次，采用 \(bool\) 类型返回值时，是一种存在性搜索，并不一定能够得到最优解。

综合以上两点，需要采取迭代化搜索，每次限制在当前层中找出一个符合条件的答案，如果找到了的话一定是最优解。

updated at 2019.4.27

迭代加深搜索的劣势在于，每次迭代的过程中，对于前面已经失败的情况，依然要重复进行搜索，会导致时间上的冗余。不过，若每一层的分支情况过多时，冗余的操作要比多搜索无用层的代价小得多。

代码如下

#include <cstdio>

#include <memory.h>

using namespace std;

const int maxn=110;

int a[maxn],n,dep;

bool dfs(int now){

	if(now==dep+1)return a[dep]==n;

	for(int i=now-1;i>=1;i--)//优化枚举顺序

		for(int j=i;j>=1;j--){

			if(a[i]+a[j]>n)continue;

			if(a[i]+a[j]<=a[now-1])break;

			a[now]=a[i]+a[j];

			if(dfs(now+1))return 1;

		}

	return 0;

}

int main(){

	while(scanf("%d",&n)&&n){

		memset(a,0,sizeof(a));

		a[1]=1;

		for(dep=1;;dep++)if(dfs(2))break;

		for(int i=1;i<=dep;i++)

			printf("%d%c",a[i],i==dep?'\n':' ');

	}

	return 0;

}