Missing Coin Sum

#include <bits/stdc++.h>

using namespace std;

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

    auto f = m.find(make_pair(final-1,sum));
    bool first = (f != m.end() and f->second);

    auto s = m.find(make_pair(final-1,sum-vec[final-1]));
    bool second = (s != m.end() and s->second);

    bool temp =  first or second or subsetExists(vec, final-1, sum, m) or subsetExists(vec, final-1, sum-vec[final-1], m);
    m[make_pair(final,sum)] = temp;
    return temp;
}


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

    map<pair<int,int>,bool> m;

    int idx=0;
    while(subsetExists(vec, n, idx, m)) 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