Missing Coin Sum

#include <bits/stdc++.h>

using namespace std;

bool subsetExists(const vector<int>& vec, int final, int sum){
    if(sum == 0) return true;
    if(sum < 0) return false;
    if(final == 0) return false;

    return subsetExists(vec, final-1, sum) or subsetExists(vec, final-1, sum-vec[final-1]);
}


int main(){
    int n;
    cin >> n;
    vector<int> vec(n);
    for(int i=0;i<n; i++) cin >> vec[i];

    int idx=0;
    while(subsetExists(vec, n, idx)) idx += 1;

    cout<< idx << endl;


}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED