CSES - Shared codeLink to this code:
https://cses.fi/paste/6e7d481ced00cb5a285d3d/
#include<iostream>
#include<vector>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int distinct_ways(vector<int>&coins,vector<vector<int>>&cache,int sum,int n)
{
if(cache[sum][n]!=-1)
{
return cache[sum][n];
}
if(sum==0)
{
return cache[sum][n]=1;
}
if(sum<0)
{
return cache[sum][n]=0;
}
if(n<=0)
{
return cache[sum][n]=0;
}
if(sum-coins[n-1]>=0)
{
return cache[sum][n]=(distinct_ways(coins,cache,sum-coins[n-1],n)
+distinct_ways(coins,cache,sum,n-1))%1000000007;
}
else
{
return cache[sum][n]=distinct_ways(coins,cache,sum,n-1)%1000000007;
}
}
void solve()
{
int n,sum;
cin>>n>>sum;
vector<int>coins(n);
vector<vector<int>>cache(sum+1,vector<int>(n+1,-1));
for(int&i:coins)
{
cin>>i;
}
cout<<distinct_ways(coins,cache,sum,n);
}
int main()
{
fastio();
solve();
return 0;
}