Subset Sum Target shows TLE when using top down DP with map implementation

#1

I have solved the subset sum target problem by using top down dp with map implementation because the range of sum is 10^7 and n can go to 5000. I have not used 2D dp array because of runtime error due to memory. So i used map but it shows tle. Please clear the doubt.

#2

@abhinandanmay11
It is great to have you back on the portal after so long
Hope you are doing great !
Please share your code so that I can look into this issue

#3

I forgot to add the code. Here is the link of code https://ide.codingblocks.com/s/224388
.

#4

@abhinandanmay11
Two issues here
Firstly you are doing recursive DP where you make stack calls which takes a lot of time for too many calls so try to shift it to bottom up DP.
Secondly you’re using a map instead. Each query runs in logn while it should be 0(1) to pass the time limit.
Please make these changes.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.