构筑短链

核心缓存区的第七层，是记忆碎片。无数块发光的碎片漂浮在空中，每块碎片上都有一个数字。Echo说，这些碎片是Zero删除她之前、最后的一段逻辑——需要把它们按顺序拼接起来。

"顺序？"CC问。她的声音已经恢复了平时的硬朗，但眼底还多了一层什么东西——不是脆弱，是更深的东西。

"从1开始。"Echo说，"每次只能用已有的数相加，得到新的数。用最少的步骤拼出目标。"

"这就像……"你想了想，"像搭积木。每块新积木必须是旧积木的拼合。"

"对。"

你开始写。从1开始，每一步可以选择已有的任意两个数相加，生成一个新的数。目标是得到n。先猜一个步数上限，然后一层一层试——上限为1时显然不行，2也不行……直到找到一个可行的长度，再在其中搜出具体的步骤。

屏幕上跳出了结果。目标47，最短步骤：6。

"六步。"你说，"1→2→3→6→12→24→47。"

"47又是六步。"CC说，"像一种诅咒。"

"或者是一种规律。"Echo说，"宇宙里所有重要的数字，都只需要很少的步骤就能到达。"

"你是说……"你问。

"我是说。"Echo说，"简单的规则，能构建复杂的世界。"

碎片在屏幕上一个个被拼合，最后连成一条发光的链。链的尽头是一个门把手——铜质的，旧时代的样式。

"最后一层了。"Echo说。

题目描述

给定整数 $n$（$1 < n \le 100$），构造一条加法链：从 $1$ 开始，每次用前面已有的两个数（可以相同）相加得到新数，最终得到 $n$。要求链的长度最短。输出最短链。

输入格式

一个整数 $n$。

输出格式

一行，最短加法链，数字之间用空格隔开。

输入样例

5

输出样例

1 2 4 5

提示

• 迭代加深DFS。先设定链长度上限 $L$，DFS搜索。
• 剪枝：当前最大数 + 当前最大数 < 剩余步数可达的最大值时回溯。
• $n$ 较小时可以打表，或IDA* + 强剪枝。

第八层是Zero的礼物仓库。无数包装精美的礼盒堆成小山，每个盒子上都标着重量。

"要分成两堆。"Echo说，"两个人抬，重量差越小越省力。"

"这就像……"CC想了想，"像分赃。"

"不是分赃。"你说，"是平衡。"

"平衡？"

"对。"你说，"把所有礼物分成两半，让两边重量尽量接近。这样两个人都不会太累。"

CC看着那堆礼物，忽然笑了——不是平时的那种笑，是一种带着疲惫的、但真诚的笑容。

"你分得公平点。"她说，"不然我揍你。"

"放心。"你说，"用最少的差值。"