Coin Change II LeetCode (Coin Change with denominations)

Solve the coin change problem and list out the denominations used.

Example 1:

coins = [1, 2, 5], amount = 11
return [1,5,5] because (11 = 5 + 5 + 1)

Example 2:

coins = [1, 3, 5], amount = 9
return [3,3,3][1,3,5] because (9=3+3+3 and 9=1+3+5)

Example 3:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

This is an extension of classical coin change problem and is also discussed in LeetCode and GeeksForGeeks. If this problem is encountered then we should assume that the interviewer is trying to check our knowledge of dynamic programming or the concept of overlapping subproblems that can also be solved by recursion (which may not be always optimal though because we solve the same problem multiple times in recursion). A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

-----------------------------------------------------------------------------------------

SOLUTION: