Skip to content

Instantly share code, notes, and snippets.

@harshraj22
Created May 31, 2019 10:28
Show Gist options
  • Save harshraj22/91cc014ba95bcbacbe4b1b9ac316f98f to your computer and use it in GitHub Desktop.
Save harshraj22/91cc014ba95bcbacbe4b1b9ac316f98f to your computer and use it in GitHub Desktop.
Getting SIGSEV
// https://practice.geeksforgeeks.org/problems/ways-to-sum-to-n/0
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll mx=1e9+7,n,m;
ll dp[1008];
vector<ll> v;
ll compute(ll sum);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int test;
cin>>test;
while(test--){
memset(dp,-1,sizeof(dp));
dp[0]=1;
ll i,j,k;
cin>>m>>n;
v.resize(m);
for(i=0;i<m;i++)
cin>>v[i];
sort(v.begin(),v.end());
cout<<compute(n)<<"\n";
}
return 0;
}
ll compute(ll sum){
if(sum<0)
return 0LL;
if(dp[sum]!=-1)
return dp[sum];
ll var=0;
for(auto it:v){
var+=compute(sum-it);
var%=mx;
}
return dp[sum]=var;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment