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

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

#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;
}