Hi I was wondering how to solve this question. The question actually came today in the weekly contest. The Question Name is -: 2952. Minimum Number of Coins to be Added . And my general approach was to just try recursion here and use pick and not pick approach to find out the element from 1 to Target. It's giving me wrong answer in the Tc -: [1,4,10] Target -: 19. My answer is 3 while the correct answer is 2. Can we try this approach to find out the answer. I know it will give the TLE but just for the practice purpose I want to try recursion here.
Submission Link -: https://leetcode.com/submissions/detail/1111336437/
You have a small mistake. This condition:
Must be checked before this other one:
Consider the case when the target can only be constructed by using the last coin. In those cases you end up with a call to
f(0, coins, coins.size()), which will return 0 but it should return 1.While your approach is correct, it wil probably not fit the time limit, even if you apply memoization. You don't really need DP to maintain the largest
[1, x]interval that has all obtainable values. (in other words, it's easy to compute and update the first non-obtainable value as you walk over the array (in sorted order), without recursion)Thankyou estoy-re-sebado for explaining. While I knew that even the memoization would be give me TLE. But thanks a lot.