Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination.
For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities are {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}. So there are 4 possibilities in total.
Let us try to solve this problem using recursion. Let N be the amount for which we have to make change, and D is the set of denominations. Assume we have a method Count which takes in the parameter amount N, and the index of current denomination, we can have pseudo code like this
Count(N, index)
Base case#1: If N < 0 or index < 0 return 0. There is no way to make change for negative numbers or if there are no denominationsBase case#2: If N == 0, return 1. There is only one possibility to make change for 0 amount, selecting none.Otherwise return Count(N, index-1) + Count( N-D[index], index ). Either ignore the current denomination (First term), or take the current denomination(second term) and recurse accordingly.
Since this recursive method solves the same problem multiple times, we can think of a dynamic programming solution for this problem. In dynamic programming, we solve the smaller sub problems first and use their results in solving bigger sub problems. We store the results in a table. Lets create a table[N+1][M] where N is the amount, and M is the denomination count.
table[0][j] = 1, Only one way to make 0.table[i][0] = 1 if N is divisible by D[0], otherwise 0
table[i][j] = table[i][j-1] if D[j] > i
= table[i][j-1] + table[i- D[j]][j]
Here is the Java code which implements the above approach.