fork download
copy 
  1. //Top down dp
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define mx 1000
  7.  
  8. int dp[50][mx+10] ,arr[mx+10];
  9.  
  10. int solve(int N,int sum)
  11. {
  12.     if(dp[N][sum]!=-1)      return dp[N][sum];
  13.     if(sum==0)              return 1;  //Base Case
  14.     if(N==0 && sum!=0)      return 0;  //Failure Base Case
  15.     else if(sum-arr[N]<0)   return dp[N][sum] = solve(N-1, sum);
  16.     else                    return dp[N][sum] = solve(N-1,sum) || solve(N-1,sum-arr[N]) ;
  17. }
  18.  
  19.  
  20. int main()
  21. {
  22.  
  23.     int N , sum;
  24.     cin>>N>>sum;
  25.     for(int i=1;i<=N;i++) cin>>arr[i];
  26.     memset(dp,-1,sizeof(dp));
  27.     if(solve(N,sum)) cout<<"YES"<<endl;
  28.     else             cout<<"NO"<<endl;
  29.     return 0;
  30. }
Success #stdin #stdout 0s 3672KB
comments (?)
stdin
copy 
5 9
1 2 3 4 5
stdout
copy 
YES
https://ideone.com/7diNnM
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!