Coin Change Problem — Printing the Combination

In this article I want to talk about the classic coin change problem and how I solved a variant of it.

Here is the problem; you have pennies(1 cent), nickels(5 cents), dimes(10 cents), and quarters(25 cents) as coins. You need to first find the least amount of coins used to make that amount and then return those coins as a map.

For example, say your input is 56 cents. Then you should return a map with the following contents:

• Nickels -> 1
• Pennies -> 1
• Dimes -> 0
• Quarters -> 2

This means that you need a nickel, a penny and two quarters at minimum to make 56 cents.

When I read the problem first I immediately knew the solution was dynamic programming (or recursion if you are living the life) and it was a variant of coin change problem.

I will leave it to you to read about the solution. I want to talk about the second part which is returning a map with the coins used.

Here is how I am doing it:

• Each time I am updating the array with a coin, I place the coin to a separate array
• The array has the mapping: id -> coin
• Then starting from the input’s coin value you traverse back and put the coins to the map.

Say that you have the input as 29. Then you will have:

• coinsUsed[29] = 25
• coinsUsed[29 – 25 = 4] = 1
• coinsUsed[4 — 3 = 2] = 1
• ….

All you have to do is to follow the thread until you reach 0. Create a set in the meanwhile and add the found coins to the array.

Here is the code as a gist: