Saleh127

Subset Sum / DP

Oct 19th, 2021
691
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-19-17.19.48
  3. ***/
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define ll long long
  7. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  8. #define get_lost_idiot return 0
  9.  
  10. int main()
  11. {
  12.    ios_base::sync_with_stdio(0);
  13.    cin.tie(0);cout.tie(0);
  14.  
  15.    ll n,m,i,j,k,l,sum;
  16.  
  17.    cin>>n>>sum;
  18.  
  19.    ll a[n+5];
  20.  
  21.    for(i=0;i<n;i++) cin>>a[i];
  22.  
  23.    bool dp[n+1][sum+2];
  24.  
  25.  
  26.    for(i=0;i<=n;i++) dp[i][0]=1;
  27.  
  28.    for(i=1;i<=sum;i++) dp[0][i]=0;
  29.  
  30.    for(i=1;i<=n;i++)
  31.    {
  32.         for(j=1;j<=sum;j++)
  33.         {
  34.              if(j<a[i-1])
  35.              {
  36.                   dp[i][j]=dp[i-1][j];
  37.              }
  38.              else
  39.              {
  40.                   dp[i][j]=dp[i-1][j] || dp[i][j-a[i-1]];
  41.              }
  42.         }
  43.    }
  44.  
  45.  
  46.    if(dp[n][sum]) cout<<"Subset sum is present"<<endl;
  47.    else cout<<"No subset sum"<<endl;
  48.  
  49.  
  50.  
  51.    get_lost_idiot;
  52. }
RAW Paste Data