TLE in Recursive code of COIN I cses

1

solution link → https://cses.fi/paste/4060ef4da6056bb522a9ca/

2

You have not written the base conditions to end the recursive calls.
You can check here

3

IN my case i am calling solve() function on when some coin[i]<= sum so sum should never be less than zero right .
for example suppose we have only coin 7 and we have to find number of permutation for 5
solve(5) → no coin less than equal to 5 so g=0
dp[5]=0;
function will end.

4

Recursive calls make your code slower. Whenever possible, avoid using recursion and try to solve dp problems iteratively.

#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;

int main() {
	int n,x;
	cin >> n >> x;
	vector<int> a(n);
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}
	vector<int> dp(x+1);
	dp[0] = 1;
	for(int j = 0;j <= x;j++){
		for(int i = 0;i < n;i++){
			if(j >= a[i]){
				dp[j] += dp[j-a[i]];
				if(dp[j] >= md)dp[j] -= md;
			}
		}
	}
	cout << dp[x];
	return 0;
}