DFS相信一定不陌生。但是迭代搜索是什么呢？让我们拭目以待！

迭代搜索会加快DFS的搜索速度。它的原理是按层搜索。依次迭代。适用于答案不在非常深的子树中。

与BFS的一个主要区别：

BFS会造成很大的空间浪费，指数级的空间会使得bfs造成崩溃。

那么我们来上一道题，This.

我们可以使迭代加深来做。

Code:

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int a[101];
int n;

bool dfs(int x, int d)
{
    if (a[x - 1] == n)
        return true;
    if (x > d)
        return false;
    bool st[101] = {0};
    for (int i = x - 1; i >= 0; i -- )
    {
        for (int j  = i; j >= 0; j -- )
        {
            int s = a[i] + a[j];
            if (st[s] || s > n || s <= a[x - 1])
            {
                continue;
            }
            st[s] = true;
            a[x] = s;
            if (dfs(x + 1, d))
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    while (cin >> n)
    {
        a[0] = 1;
        if (n == 0)
        {
            return 0;
        }
        int d = 1;
        while (dfs(1, d) == 0)
        {
            d ++;
        }
        if (n == 1)
        {
            cout << 1 << endl;
            continue;
        }
        for (int i = 0; i <= d; i ++ )
        {
            printf("%d ", a[i]);
        }
        printf("\n");
    }
    return 0;
}

The end.