Coin Combinations II

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007;

#define got cout<<"YES\n"; return;
#define got0 cout<<"YES\n"; return 0;

#define bhak cout<<"NO\n"; return;
#define bhak0 cout<<"NO\n"; return 0;

#define bas cout<<"\n";



ll getAns(ll i, ll sum, ll n, vector<ll> &vec, vector<vector<ll>> &dp){
    if(sum==0){
        return 1;
    }

    if(sum<0){
        return 0;
    }

    if(i==n){
        return 0;
    }

    if(dp[i][sum]!=-1){
        return dp[i][sum];
    }

    ll pick = getAns(i, sum-vec[i], n, vec, dp)%MOD;
    ll notPick = getAns(i+1, sum, n, vec, dp)%MOD;

    return dp[i][sum] = (pick + notPick)%MOD;
}

ll getAnsTab( ll sum, ll n, vector<ll> &vec){
    vector<vector<ll>> dp(n+1, vector<ll> (sum+10, 0));

    for(int i=0; i<=n; ++i){
        dp[i][0] = 1;
    }

    for(int s=1; s<=sum; ++s){
        dp[n][s] = 0;
    }

    for(int i=n-1; i>=0; --i){
        for(int j=0; j<=sum; ++j){
            ll notPick = dp[i+1][j]%MOD;
            ll pick = 0;

            if(j-vec[i]>=0){
                pick = dp[i][j-vec[i]];
            }

            dp[i][j] = (pick + notPick)%MOD;
        }
    }

    return dp[0][sum];
}


ll getAnsOpt( ll sum, ll n, vector<ll> &vec){
    // vector<vector<ll>> dp(n+1, vector<ll> (sum+10, 0));
    vector<ll> next(sum+10, 0); // point at i==n at strat
    vector<ll> curr(sum+10, 0); // Point from i==n-1

    // for(int i=0; i<=n; ++i){
    //     dp[i][0] = 1;
    // }
    next[0]=1, curr[0]=1;

    for(int s=1; s<=sum; ++s){
        // dp[n][s] = 0;
        next[s] = 0;
    }
    ll pick, notPick;
    for(int i=n-1; i>=0; --i){
        for(int j=0; j<=sum; ++j){
            // ll notPick = dp[i+1][j]%MOD;
            notPick = next[j]%MOD;

            pick = 0;

            if(j-vec[i]>=0){
                // pick = dp[i][j-vec[i]];
                pick = (curr[j-vec[i]])%MOD;
            }

            // dp[i][j] = (pick + notPick)%MOD;
            curr[j] = (pick + notPick)%MOD;
        }
        swap(curr, next);
    }

    // return dp[0][sum];
    return next[sum];
}



int main() {
    // your code goes here
    ll  n, sum; cin>>n>>sum;
    vector<ll> vec(n);
    for(ll i=0; i<n; ++i){
        cin>>vec[i];
    }


    // vector<vector<ll>> dp(n+1, vector<ll> (sum+10, -1));

    ll ans = getAnsOpt(sum, n, vec);

    cout<<ans;
    bas

    return 0;
}