原题链接：https://www.acwing.com/problem/content/172/
题目描述：
满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”： 1、X[1]=1 2、X[m]=n 3、X[1]<X[2]<…<X[m-1]<X[m] 4、对于每个 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判断是否有合法解。从第一个位置开始，依次枚举每个空位的的可能数字。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std
;
const int N
= 110;
int path
[N
];
int n
;
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
<= path
[u
- 1]||s
> n
|| 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;
}
