POJ 2248 Addition Chains (迭代加深搜索， 进阶指南)

算法竞赛进阶指南，110 页
题目意思：
求满足下列条件的数列。
?a0 = 1
?am = n
?a0 <a1 <a2 <… <am-1 <am
对于每个k（1 <= k <= m），存在两个（不一定不同的）整数i和j（0 <= i，j <= k-1），其中ak = ai + aj

注意：
1、假设序列的长度为 depth ，依次增加长度，再深搜，直到找到满足要求的序列
2、假设当前已经选好的序列为 path[1], path[2], … , path[u]
path[u + 1] 等于前 u 个数中的两个数相加 path[u + 1] = path[i] + path[j] (1 <= i, j <= u);
枚举的时候, 先枚举path[u + 1] 可能取得的大数值；
3、 用 vis[MaxN] 数组记录当前所在的额 dfs 函数中，哪些 path[u + 1] 值是已经搜过的，避免重复；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MaxN = 110;
int path[MaxN];
int n;bool dfs(int u, int depth)	// u 表示当前已经枚举了多少个数
{
    if(u == depth){
    return path[u] == n;	}bool vis[MaxN] = {
    false};for(int i = u; i >= 1; --i){
    for(int j = i; j >= 1; --j){
    int s = path[i] + path[j];if(s > path[u] && vis[s] == false && s <= n){
    path[u + 1] = path[i] + path[j];vis[s] = true;if(dfs(u + 1, depth)){
    return true;}}}}return false;
}int main()
{
    path[1] = 1;while(scanf("%d", &n) != EOF && n){
    int depth = 1;while(dfs(1, depth) == false){
    ++depth;}for(int i = 1; i <= depth; ++i){
    printf("%d", path[i]);if(i < depth){
    printf(" ");}else{
    printf("\n");}}}return 0;
}/* 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 */