深さ判別法

n個の数列a0,…,anがあたえられたとき、その数列を組み合わせて得られた和がkであるかどうか判別するアルゴリズムを深さ判別法で解く

深さ判別法は全探索のアルゴリズムで、 オーダーはO(2^n)であるので、n=20程度であれば、解くことが出来る。それ以上になる場合は効率的なアルゴリズムを考えなければならない。

#include <iostream>
#include <vector>
using namespace std;

int n,k;
vector<int> a;

bool dps(int i, int sum){
    if(sum == k) return true;
    else if(i == a.size()) return false;
    if(dps(i+1,sum + a[i])) return true;
    if(dps(i+1, sum)) return true;
    return false;
}

int main(){
    cin >> n;
    for (int i = 0;i < n; i++){
        int m;
        cin >> m;
        a.push_back(m);
    }
    cin >> k;
    bool ans = dps(0,0);
    cout << ans <<endl;
    return 0;
}

input (標準入力)
4
1 2 4 7
13

output (標準出力)
1