思路与算法

以加法次数为深度做迭代加深DFS。深度从ceil(log2 n)开始，每次枚举任意两个已有项的和，要求严格大于当前末项且不超过n，去除同层重复和。若当前最大项再连续倍增剩余次数仍小于n，则剪枝。找到第一条链后输出。

正确性说明

每一步新值至多是此前最大值的2倍，所以ceil(log2 n)是合法深度下界，倍增剪枝不可能删去可达目标的分支。任意合法后继都等于某两个已知项之和，枚举所有这些和且只去除数值相同的分支，不漏一般加法链。按深度递增，首次成功之前所有更短链均被穷尽，因此输出长度最小。独立BFS另已覆盖完整教学域1..100最短长度。

复杂度

初始化路径O(1)。设最优加法次数为d，每层至多O(d²)候选枚举，回溯为指数级搜索；可宽松写O(n^d d²)，空间O(d+n)含去重数组与栈。存在二进制构造保证d不超过floor(log2 n)+popcount(n)-1；完整1..100及最多100组输入已按原资源实测。

易错点

不能只枚举末项加某旧项的星形链来冒充一般加法链。要允许同一个旧项加自己。n=1只输出1。0是输入终止符，不生成答案；多条最短链全部允许，由特判检查每项合法和最短项数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int target, depth;
vector<int> chain;
bool dfs(int left) {
    int last = chain.back();
    if (!left)
        return last == target;
    if ((last << left) < target)
        return false;
    bool seen[101] = {};
    vector<int> next;
    for (int i = (int)chain.size() - 1; i >= 0; --i)
        for (int j = i; j >= 0; --j) {
            int v = chain[i] + chain[j];
            if (v > last && v <= target && !seen[v]) {
                seen[v] = true;
                next.push_back(v);
            }
        }
    sort(next.rbegin(), next.rend());
    for (int v : next) {
        chain.push_back(v);
        if (dfs(left - 1))
            return true;
        chain.pop_back();
    }
    return false;
}
int main() {
    while (cin >> target && target) {
        depth = 0;
        while ((1 << depth) < target)
            ++depth;
        for (;; ++depth) {
            chain = {1};
            if (dfs(depth))
                break;
        }
        for (int i = 0; i < (int)chain.size(); ++i)
            cout << (i ? " " : "") << chain[i];
        cout << '\n';
    }
}