$$\color{Red}{加成序列——DFS之迭代加深}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

满足如下条件的序列 X（序列中元素被标号为 1、2、3…m）被称为“加成序列”：

X[1]=1
X[m]=n
X[1]<X[2]<…<X[m−1]<X[m]对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得 X[k]=X[i]+X[j]。
你的任务是：给定一个整数 n，找出符合上述条件的长度 m 最小的“加成序列”。

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

输入格式

输入包含多组测试用例。

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

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

输出格式

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

每个输出占一行。

数据范围

1 ≤ n ≤ 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

思路

这道题是迭代加深模型。即每当我们的DFS加深一层，时间复杂度是指数级的增长，这个增长在层数稍微增加，会比前面每层遍历的枚举数量之和还要大。

但有些题目如本题，层数是可以预料到的，见多重背包问题 ，存在二进制分堆的思想，即如果满足序列是二进制增长，这些数可以满足表示任何小于等于集合元素之和的数。

故我们可以进行迭代加深，但是本题的限制其实不需要严格满足二进制分堆，这里只是暗示，数字的选取，比二进制分堆的数会更少。

我们初始化第一个节点即已知的 path[0] = 1为第一层，逐步加深搜索，因为本题保证一定有解，如果是无解题目可以在无解的层数直接返回失败。

u 为当前正在搜索的层数， 而 depth 为最大能搜索的层数

剪枝需要做单调性判断，且为了防止同一层的选择出现重复性求和判断，开辟了一个只在本层的局部数组st，锁定每次选出的数的状态。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N = 110, n;
    static int[] path = new int[N];


    static boolean dfs(int u, int depth){
        if (u == depth) return path[u - 1] == n;

        // 开局部变量 是因为这个状态只能影响到这一次dfs枚举的选择
        // 如  n == 10   防止枚举过  1  9  又枚举了   2  8 等情况 这是本层决策 与下一层无关
        boolean [] st = new boolean[N];

        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, depth)) return true;
            }
        }

        return false;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        path[0] = 1;
        while (true) {
            n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            // 初始化每次开局层数为1,即只有一个根节点 1
            int depth = 1;
            while (!dfs(1, depth)) depth++;

            // 输出答案
            for (int i = 0; i < depth; i++) System.out.print(path[i] + " ");
            System.out.println();
        }
    }
}