POJ 2248 Addition Chains

問題

要素が一つだけの数列a(a[0] = 1)からはじめて、数列a中の任意の2つの要素の和を取り、それが最終項より大きい場合に最終項の後ろにくっつけるという操作を繰り返して、入力として与えられるnをつくりたい。
操作回数が最小であるときの、最終的な数列を出力せよ。複数パターンある場合はどれか一つで良い。

やりかた

なにかうまい方法があるだろうと思ったが、調べるとshortest addition chain（最短加法鎖）問題といってNP完全に属する問題のようだ。
Addition chain - Wikipedia
A003313 - OEIS

ただ今回は入力が小さいので全探索でも通る。
ノードが数列になっている多分木（探索のイメージ）を、ある深さ以上は調べないという枝刈りを入れて探索したら通すことができた。

BFSのほうが直感的だったので、最初はvectorに入れた数列を状態としてBFSで頑張ったけど何度やってもTLEした。探索しているノードのみ数列を持つDFSに切り替えたら一瞬だった。

以下ソース。

int n;
int arr[12];
vector<int> ans[110];

void rec(int idx){
  int last = arr[idx];
  if(last > 100 || idx > 9) return;
  if(ans[last].size() > idx + 1){
    ans[last].resize(idx + 1);
    for(int i = 0; i < idx + 1; i++) ans[last][i] = arr[i];
  }

  for(int i = 0; i <= idx; i++){
    arr[idx + 1] = arr[idx] + arr[i];
    rec(idx + 1);
  }
  return;
}

int main(int argc, char **argv){
  fill(ans, ans + 101, vector<int>(100, 0));
  arr[0] = 1;
  rec(0);
  while(cin >> n, n){
    for(int i = 0; i < ans[n].size(); i++) 
      cout << ans[n][i] << " ";
    cout << endl;
  }
  return 0;
}