满足如下条件的序列被称为加成序列：
X[1]=1,X[m]=n,X[1]<X[2]<......<X[m-1]<X[n]
对于每个k(2<=k<=m)都存在两个整数i和j（1<=i,j<=k-1,i,j可以相等），使得X[k]=X[i]+X[j]。
给定一个n，找出符合上述条件的长度m最小的加成序列，多个答案输出一个即可。n<=100
搜索，对于当前位置k，可以有任意两个i,j相加得出，所以我一开始是两层循环（菜死了）然后得出k再搜索k+1。
但任意两个i,j只需要i不变，j从1到k-1枚举得出的答案就和两个i,j得出的一样。只是顺序不同，不影响两者的和。
然后加入以下剪枝：
1.优化搜索顺序：为了尽快得到n，尽量从大到小枚举
2.排除等效冗余，就是加入一个数组判重
3.迭代加深，因为长度m的值不会太大（<=10），而每次搜索每个数的和，分支很多。所以可以限制搜索深度。
4.如果当前这个数连续翻倍m-k次后还是比n小，那么就可以返回。
代码如下：
#include <iostream> #include <stdio.h> #include <queue> #include <vector> #include <cmath> #include <string.h> using namespace std; int n,arr[233],p,vis[233],ansr[233],ans; int lim; bool flag; int pow(int a,int b) { int ret=1; while(b){ if(b&1) ret=ret*a; a=a*a; b>>=1; } return ret; } void dfs(int x) { if(x==lim){ if(arr[x-1]==n){ flag=true; for(int i=1;i<=x-1;++i) ansr[i]=arr[i]; } return ; } if(flag) return ; if(arr[x-1]*pow(2,lim-x)<n) return ; for(int i=x-1;i>=1;--i){ if(vis[arr[x-1]+arr[i]]) continue; vis[arr[x-1]+arr[i]]=1; arr[x]=arr[x-1]+arr[i]; dfs(x+1); vis[arr[x-1]+arr[i]]=0; } } int main() { while(scanf("%d",&n),n){ arr[1]=1; memset(vis,0,sizeof vis); memset(ansr,0,sizeof ansr); vis[1]=1; for(lim=2;lim<=11;lim++) { flag=false; //memset(vis,0,sizeof vis); //p=1; dfs(2); if(flag) break; } for(int i=1;i<lim-1;++i) printf("%d ",ansr[i]); printf("%d ",ansr[lim-1]); } return 0; }