分析

• 我们依次枚举下一个是什么。

• 考虑如何剪枝：

（1）优化搜索顺序：优先枚举较大的数，这样之后的分支比较少。

（2）排除等效冗余：当我们枚举当前位置填写什么数据时，我们需要遍历前面的任意两个数加和得到的数据，可以会有重复，我们需要排除这些重复的数据，可以在每个节点中开一个判重数组。

（3）可行性剪枝：当前空位中所填写的内容不能与所在行、列、九宫格有重复数组。

（4）最优性剪枝：无。

• 使用迭代加深，层数从1开始（因为至少有一个数1）。如果没有答案，深度加一，继续下一轮搜索。

#include <iostream>

using namespace std;

const int N = 110;

int n;
int path[N];  // 记录答案

// u: 当前搜索的深度; k: 迭代加深的深度
bool dfs(int u, int k) {

    if (u == k) return path[u - 1] == n;

    bool st[N] = {0};
    for (int i = u - 1; i >= 0; i--)
        for (int j = i; j >= 0; j--) {
            int s = path[i] + path[j];
            if (s > n || s <= path[u - 1] || st[s]) continue;
            st[s] = true;
            path[u] = s;
            if (dfs(u + 1, k)) return true;
        }
    return false;
}

int main() {

    path[0] = 1;
    while (cin >> n, n) {
        int k = 1;  // 迭代加深的深度
        while (!dfs(1, k)) k++;

        for (int i = 0; i < k; i++) cout << path[i] << ' ';
        cout << endl;
    }

    return 0;
}