Why i am getting TLE in coin combination ii?

help
,
1

I am solving cses coin combination ii problem using top-down approach and getting TLE. Is i used memoization correctly??
Problem link CSES - Coin Combinations II
Solution link https://cses.fi/paste/6e7d481ced00cb5a285d3d/
I also went through gfg solution(top-bottom) but it is also not optimised(giving TLE).
gfg solution link Coin Change | DP-7 - GeeksforGeeks
Please help!!!

2

If the approach is correct but gives TLE, implementation has to be optimised. You might want to try the iterative approach as well. Because recursion is costlier because of the return statement.

1 Like
3

Yes, you are correct. iterative approach is working just fine.
but i want a recursive solution. If you have any resource then please help!!
Thanks for replying…

4

I already mentioned.

Recursion is not bad always. The problem had the following constraints.

1\le n\le100
1\le x \le 10^6
1\le c_i\le 10^6

Recursion will add a very huge number of costly operations (here it is the return statement).

Your solution will definitely pass if the constraints are relaxed a bit.

1 Like
5

Got it ! Thankyou very much

6

any recursive solution possible in this problem?