迭代加深DFS

原理

见《进阶指南》第109页。

模板题

AcWing-170-加成序列

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
int n, x[N], max_dep;

bool dfs (int cur) {
    if (cur == max_dep + 1) // 递归边界
        return x[max_dep] == n;
    
    bool mark[N];
    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= cur - 1; ++ i) {
        for (int j = 1; j <= cur - 1; ++ j) {
            int sum = x[i] + x[j];
            if (mark[sum] == false
                && x[cur - 1] < sum
                && sum <= n
            ) {
                mark[sum] = true;
                x[cur] = sum;
                if (dfs(cur + 1) == true) return true;
            }
        }
    }
    return false;
}

int main () {
    x[1] = 1;
    while (cin >> n && n) {
        max_dep = 1;
        while (dfs(2) == false) ++ max_dep;
        for (int i = 1; i <= max_dep; ++ i)
            cout << x[i] << ' ';
        cout << endl;
    }
    return 0;
}