[Java] Calculate minimum number of coins necessary to make a given amount

This is a common problem, given a target amount N and a set of coins M with different denominations, what is the minimum number of coins necessary to make the desired amount, if at all possible.

Coins have all integer positive values. If amount cannot be generated, return -1.

The textbook approach would be dynamic programming where we find out which calculation to perform at each step and cache calculated values for future reference to reduce the computation time at the cost of space.

However, one can notice that this problem can also be tackled with a BFS graph search, where nodes are the possible amounts and edges are the coin denominations. New nodes are calculated by subtracting a coin from the current amount. 

If the result of a subtraction would yield a negative amount, we skip that path as there is no possible way to reach the desired amount with those choices.

Since BFS will ALWAYS encounter the node matching our target first, we are ensured by then we have our result, in this case the minimum number of coins.

For example: target is 10 and coins are 1, 3, 5. Our graph would look like this:

                                  10

              /                    |                  \

           9                     7                     5

      /   |   \               /   |   \            /   |    \

    8     6    4            6     4    2           4    2    0

  / |\    /|\  /|\ .....

.....

And so on. Notice that the first time we reach a node we followed the fastest way to get there, therefore when we would travel to an already discovered node, we can stop going down our path since our path would use more coins than the existing one and therefore won't lead to the solution.

Additionally, the first time we encounter a node with value 0, we know we have our answer. If we explore the graph without reaching a node with value 0, it means the given amount cannot be made with the given coins and therefore there is no answer.

Another noticeable thing, is that we use a map to retrieve data while exploring, however, there is no need to keep all the data in the map at all times, since after we explored a node, we won't ever go back there again, therefore a small space optimization can be to remove nodes after they are visited.

As last observation, the Map is not mandatory if one can track nodes in the form (amount, minCoinsSoFar) AND can use a Set then to store already visited nodes.

The overall runtime is O(NxM) and space is O(N).

You can find my implementation of minimumCoinsForChange on my Gist along with some test cases in MinimumCoinsForChangeJTests.