[Java] Calculate in how many ways can a target integer be reached using a given set of step increments

Very similar to finding the minimum amount of coins to make a certain amount, we have another problem: given a target number and a set of step increments, calculate in how many ways can we reach the target starting from 0. If the target cannot be reached, return -1.

As in the previous case, dynamic programming would help reduce the time needed to reach a solution, however our trusty BFS approach can also be applied here, we just need a couple tweaks in the logic.

Example: target is 4 and steps are 1, 2. Our graph now would be:

           0

       /      \

      1        2

     /  \      /  \

    2   3      3   4

   / \    \     \

  3  4     4     4

/

4 

If you count the leaves, the result is 5 possible ways. Now notice that as long as we keep going down a specific path, we do NOT increase the number of ways we can get to our target, in fact, the full path IS one way of reaching the target, therefore when we deviate, eg when we have more than one link to follow moving forward, we increase the number of ways since we are making a new path.

Additionally, the faster routes (using bigger step increments) will reach a specific node faster than routes following smaller increments. This is again guaranteed by the nature of the BFS. We therefore know, that once we encounter an already discovered node, we were the last ones to get there. The number of ways to reach that node can therefore be updated to include the number of ways to reach us and we can stop exploring that route.

If instead we reach an undiscovered node, the number of ways to reach it, is exactly equal to the number of ways to reach us since we were the first to get there.

By tracking for each node the number of ways we can get there in a separate map, we can easily find the solution. If the map does NOT contain an entry for the target, it means it was impossible to reach given the provided steps.

We can again remove an entry from the map after we visited it, since we won't ever get back there again.

The complexity is O(NxM) and space is O(N).

You can find my implementation of howManyWaysforTarget on my Gist along with some tests in HowManyWaysForTargetJTests.