I have a question about the coin change problem where we not only have to print the number of ways to change $n with the given coin denominations for eg {1,5,10,25}, but also print the ways
For example if the target = $50, and the coins are {1,5,10,25}, then the ways to actually get use the coins to get the target are
- 2 × $25
- 1 × $25 + 2 × $10 + 1 × $5
- etc.
What is the best time complexity we could get to solve this problem? I tried to modify the dynamic programming solution for the coin change problem where we only need the number of ways but not the actual ways
I am having trouble figuring out the time complexity. I do use memorization so that I don't have to solve the same problem again for the given coin and sum value but still we need to iterate through all the solution and print them. So the time complexity is definitely more than O(ns) where n is the number of coins and s is the target Is it exponential? Any help will be much appreciated