リハビリ

プログラミングコンテストチャレンジブックを読み始めた.リハビリに問題を解いてみる.まず初めの問題.
4回連続でくじを引く時,くじを引いては戻して引いては戻してを繰り返す.
この時,引いたくじの合計がmになる時Yes,そうでない時,Noと出力.
くじの数は,nとする.くじのナンバーは与えられる.

まず普通に,深さ優先探索.

int n,m;
vector<int> num;

bool htansaku(int sm,int k){
  if(sm == m && k==0){
    return true;
  }else if(sm > m)
    return false;
  if(k==0)
    return false;
  
  for(int i=0;i<num.size();i++){
    ans.push_back(num[i]);
    if(htansaku(sm+num[i],k-1))
      return true;
    ans.pop_back();
  }
  return false;
}

次に,mから各くじの値を４回引いていく.

int n,m;
vector<int> temp;
vector<pair<int,int> > test;

int main(){
  cin >> n >> m;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    temp.push_back(a);
  }
  test.push_back(pair<int,int>(0,m));

  for(int i=0;i<4;i++)
    for(int j=0;j<test.size();j++)
      if(test[j].first==i)
	for(int k=0;k<temp.size();k++)
	  test.push_back(pair<int,int>(i+1,
				       test[j].second-temp[k]));
  bool flag = false;
  for(int i=0;i<test.size();i++){
    if(test[i].first == 4 && test[i].second == 0){
      flag = true;
      break;
    }
  }
  if(flag)
    cout << "Yes";
  else
    cout << "No";
  cout << endl;
  return 0;
}

と書いてみて気付いたけどどちらもO(n^4)で等しい.下の方は無駄なことしている分遅いと思う.もっと早くするには?
と考えると,O(m^4)のアルゴリズムが思いつくけどもっと遅くなっている！？