recursive approach

 avatar
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