It is not limited to this problem , I have encountered this issue since the first week i started with basic recursion and thought why not do this So in this first submission , i am calculating total value in knapsack like problem and at the end when there is nothing more left , i return the total answer . It gives tle as expected https://www.codechef.com/viewsolution/1010917404 However in the second submission when i try to memoize it , I get a wrong answer https://www.codechef.com/viewsolution/1010917299 At the end when i return 0 in the invalid case and add the value at each layer instead , i get correct answer https://www.codechef.com/viewsolution/1010939008

Why is first submission fine when i don't memoize it .