部分和問題を再帰全探索で書いてみた（けんちょん本 4.5）

ここのところスランプを感じてます。本業でとびきり重たい事件に忙殺されてることもあって，精進も上滑りだし，コンテストは冷えるしなのですが，ほそぼそ精進と勉強は続けています。

精選がDFSやBFS，個数制限なしナップサックなどが頭が回らなくて厳しく詰まったので，けんちょん本と数学ガールを中心にやってます。

けんちょん本は４章で再帰の練習。

部分和問題を再帰全探索で書いてみました。
なんとか自力でかけました。

#include <bits/stdc++.h>
using namespace std;

int N,W;
int a[100];

bool func(int i,int w){
  if(i==0){
    if(w==0){
      return 1;
    }
    else{
      return 0;
    }
  }
  if(func(i-1,w)||func(i-1,w-a[i-1]))return 1;
  return 0;
}

int main(){
  cin>>N>>W;
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
  
  if(func(N,W)){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  return 0;
}

検討

けんちょん本のコード4.9では再帰関数の引数として入力配列を与えているところが違いました。

グローバルにおいておけば関数の引数に入力配列を入れとかなくても大丈夫だと思いますが，違いについて，もう少しじっくり考えてみます。