recursive approach
meda
c_cpp
a month ago
962 B
7
Indexable
#include<bits/stdc++.h> using namespace std; int main(){ int n, S; cin >> n >> S; vector<int> a(n + 1); for(int i = 1; i <= n; i ++) cin >> a[i]; vector<vector<int>> memo(n + 1, vector<int>(S + 1, -1)); // memo[i][j] = -1 -> not visited yet // memo[i][j] = 0 -> computed before and the answer is no // memo[i][j] = 1 -> computed before and the answer is yes function<int(int, int)> f =[&] (int pos, int sum){ // invalid if(sum < 0) return 0; // Can not achieve a sum > 0 using 0 elements. if(pos == 0) return (int)(sum == 0); // if computed before cut the recursive tree if(memo[pos][sum] != -1) return memo[pos][sum]; int op1 = f(pos - 1, sum - a[pos]); // take the element int op2 = f(pos - 1, sum); // leave the element return memo[pos][sum] = (op1 || op2); }; cout << (f(n, S) ? "CAN" : "CANNOT") << endl; }
Editor is loading...
Leave a Comment