読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

全探索 整数を作れるかの問題

配列の要素から整数を作れるかを判定する関数

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

static const int MAX_N = 1000;
int n;//配列Aの大きさ
int m;//判定する整数
int A[MAX_N];

bool solve(int i,int m){
    /*
        整数mが作れるか否かの再起関数
    */
    if(m==0)return true;
    if(i>=n)return false;
    return solve(i+1,m) || solve(i+1,m-A[i]);
}

int main()
{
    cin>>n;
    cout<<"判定する整数"<<endl;
    cin>>m;
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    cout<<(solve(0,m)?"possible":"impossible")<<endl;
    return 0;
}
bool solve(int i,int m){
    /*
        整数mが作れるか否かの再起関数
    */
    if(m==0)return true;
    if(i>=n)return false;
    bool res1 = solve(i+1,m);//A[i]を使わない
    bool res2 = solve(i+1,m-A[i]);//A[i]を使う
    bool res = res1 || res2;
    return res;
}