加成序列

170. 加成序列 - AcWing题库 满足如下条件的序列 $X$（序列中元素被标号为 $1、2、3\dots m$）被称为“加成序列”：

1. $X[1]=1$
2. $X[m]=n$
3. $X[1]<X[2]<\dots <X[m-1]<X[m]$
4. 对于每个 $k$（$2\le k\le m$）都存在两个整数 i 和 j （$1\le i,j\le k-1$，$i$ 和 $j$ 可相等），使得 $X[k]=X[i]+X[j]$。

你的任务是：给定一个整数 $n$，找出符合上述条件的长度 $m$ 最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

输入格式

输入包含多组测试用例。

每组测试用例占据一行，包含一个整数 $n$。

当输入为单行的 $0$ 时，表示输入结束。

输出格式

对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。

每个输出占一行。

数据范围

$1\le n\le 100$

输入样例：

5
7
12
15
77
0

输出样例：

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

思路

没思路就考虑爆搜, 搜索顺序： u 为当前是第几项, path数组记录当前的数列 1 2 3 … 枚举当前项的值是什么, 从之前几个数相加得出

优化剪枝：

1. 值越大的分支越少, 从大到小枚举之前的组合
2. 1+3 和 3+1 得出的值相同, 故以组合方式枚举
3. 同样的 2+3 和 1+4 的值也相同, 在搜索时声明st布尔数组判断某数是否被没举过
4. 简单给一个数128, 显然1 2 4 8 16 32 64 128是最短的序列, 其搜索深度为8, 这给了一个启示, 题目n<100, 也就是说正解的层数不深, 但我们如果枚举所有情况的话会搜的非常深, 故可以使用迭代加深优化。

代码

const int N = 110;
int path[N];
int n;
 
bool dfs(int u, int depth)
{
    if(u > depth) return false; // 搜到最后还没搜到就是失败了
    if(path[u - 1] == n) return true;
 
    
    bool st[N] = {0};
    for(int i = u - 1; i >= 0; i--)
        for(int j = i; j >= 0; j--)
        {
            int t = path[i] + path[j];
            if(t > n || st[t] || t <= path[u - 1]) continue;
            
            st[t] = true;
            path[u] = t;
            if(dfs(u + 1, depth)) return true;
        }
    return false;
}
 
int main()
{
    path[0] = 1;
    while(cin >> n, n)
    {
        int depth = 1;
        while(!dfs(1,depth))
            depth++;
        for(int i = 0; i < depth; i++)
            cout << path[i] << " ";
        cout << endl;
    }
    return 0;
}