满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：
1、X[1]=1
2、X[m]=n
3、X[1]<X[2]<…<X[m-1]<X[m]
4、对于每个 kk（2≤k≤m2≤k≤m）都存在两个整数 ii 和 jj （1≤i,j≤k−11≤i,j≤k−1，ii 和 jj 可相等），使得X[k]=X[i]+X[j]。
你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
输入格式
输入包含多组测试用例。
每组测试用例占据一行，包含一个整数n。
当输入为单行的0时，表示输入结束。
输出格式
对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。
每个输出占一行。
深度优先搜索（dfs）每次选取一个分支， 不断深入， 直到到达递归边界才回溯， 但这种策略有一定的缺陷， 假如搜索树每个节点的分支数目从非常多， 并且问题的答案在某个较浅的节点上。如果一开始就选错了分支， 就很可能在不包含答案的深层子树上浪费许多时间；所以限制每次限制搜索的深度d， 多次搜索， 这和重复搜索与深层子树的规模来比， 实在是小巫见大巫了；
这道题可以看出， m的规模不会太大（<=10），所以我们用迭代加深的搜索方式， 从1开始限制深度， 若搜索失败就增加深度限制重新搜索， 直到找到一组解为止；
#includeusing namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int MAXN = 2e6 + 100;const int MAXM = 3e3 + 10;template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff;}template < typename T > inline void write(T x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0');}int n, a[MAXN];bool vis[MAXN];int dfs(int now, int deep, int val) { if(a[now] == n) return now; if(now > deep) return 0; for(int i = now; i >= 1; --i) { for(int j = i; j >= 1; --j) { if(!vis[a[i] + a[j]] && a[i] + a[j] > val && a[i] + a[j] <= n) { vis[a[i] + a[j]] = true; a[now + 1] = a[i] + a[j]; int flag = dfs(now + 1, deep, a[now + 1]); if(flag) return flag; vis[a[i] + a[j]] = false; a[now + 1] = 0; } else if(a[i] + a[j] <= val) break; } } return 0;}int main() { while(scanf("%d", &n) && n) { if(n == 1) { puts("1"); continue; } for(int i = 2; i <= 10; ++i) { memset(a, 0, sizeof(a)); memset(vis, false, sizeof(vis)); a[1] = 1; a[2] = 2; int top = dfs(2, i, 0); if(top) { for(int i = 1; i <= top; ++i) { write(a[i]); putchar(' '); } puts(""); break; } } } return 0;}