一.题目链接：

POJ-2248

二.题目大意：

序列 x 有如下性质：

① x[1] = 1

② x[m] = n

③ x[1] < x[2] < ... < x[m - 1] < x[m]

④ 对于每个 k （2 ≤ k ≤ m），都存在 两个整数 i，j （1 ≤ i，j ≤ k - 1），使得 x[k] = x[i] + x[j].

题目给出 n，要求构造出序列 x.

三.分析：

迭代加深裸题.

对当前的x[cur] 枚举前面的 i 和 j 即可.

剪枝：

① 优化搜索顺序：

从大到小枚举 i，j，使得序列中的数尽快逼近 n.

② 排除等效冗余：

对于不同的 i 和 j，x[i] + x[j] 可能相等，这里加一个数组标记一下，不重复搜索搜索失败的数字.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;

const int M = (int)1e5;
const int mod = 99991;
const int inf = 0x3f3f3f3f;

int ans[105];
int n, deep;

bool dfs(int cur)
{
    if(cur == deep)
        return ans[deep] == n;
    bool fail[105];
    memset(fail, 0, sizeof(fail));
    for(int i = cur; i; --i)
    {
        for(int j = i; j; --j)
        {
            int num = ans[i] + ans[j];
            if(num <= n && num > ans[cur] && !fail[num])
            {
                ans[cur + 1] = num;
                if(dfs(cur + 1))
                    return 1;
                fail[num] = 1;
            }
        }
    }
    return 0;
}

int main()
{
    ans[1] = 1;
    while(~scanf("%d", &n) && n)
    {
        deep = 1;
        while(!dfs(1))
            ++deep;
        for(int i = 1; i <= deep; ++i)
            printf("%d%c", ans[i], i == deep ? '\n' : ' ');
    }
    return 0;
}