Why Coin Combinations II problem in CSES geting TLE by recursive solution? but iterative solution in accepted.
My recursive code is here:
#include<bits/stdc++.h>
using namespace std;
// #define int long long
int n, m, p, mod=1e9+7, ans=0; vector<vector<int>>dp(110, vector<int>(1e6+9, -1));
vector<int>v;
int ok(int p, int i){
// cerr<<p<<'\n';
if(p==0) return 1;
if(p<0 || i==n) return 0;
if(dp[i][p]!=-1) return dp[i][p];
int k=0;
k=(k+ok(p-v[i], i)); if(k>mod) k-=mod;
k=(k+ok(p, i+1)); if(k>mod) k-=mod;
return dp[i][p]=k;
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m; v.resize(n); for(int i=0; i<n; i++) cin>>v[i]; //sort(v.begin(), v.end());
cout<<ok(m, 0)%mod<<'\n';
}
vector<vector<int>>dp(110, vector<int>(1e6+9, -1))this line is the reason total number of array elements should be <1e7 for safe operation yours can go upto 1e8, i was also getting runtime error
Your recursive solution is getting TLE because it does not use memoization
Every call to your function ok(p, i) explores two branches:
one including the coin (ok(p — v[i], i))
one skipping it (ok(p, i + 1))
Without memoization, the number of recursive calls grows exponentially — leading to a time complexity of: O($$$2^n \cdot m$$$) which is very slow for larger inputs.
While iterative is O($$$n \cdot m$$$)
There was a blog concerning about compiler optimizations regards to this problem. You should check this out: https://codeforces.me/blog/entry/131922.