Objective: Given a set of coins and amount, Write an algorithm to find out how many ways we can make the change of the amount using the coins given.

This is another problem in which i will show you the advantage of Dynamic programming over recursion.

Example:

Amount = 5
coins [] = {1,2,3}
Ways to make change = 5
{1,1,1,1,1} {1,1,1,2}, {1,2,2}, {1,1,3} {2,3}

Approach:

Recursive Solution:

We can solve it using recursion.

For every coin we have an option to include it in solution or exclude it.

See the Code

Code:

Time Complexity : 2^{n}

I have been asked that by many readers that how the complexity is 2^n . So including a simple explanation-

For every coin we have 2 options, either we include it or exclude it so if we think in terms of binary, its 0(exclude) or 1(include). so for example if we have 2 coins, options will be 00, 01, 10, 11. so its 2^2. for n coins , it will be 2^n. In all these options we will be checking whether that selection has made the change which is required.

But if we notice that we are solving many sub-problems repeatedly.

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Hi, if I understand correctly, in recursive implementation the third condition should be (i 0), not (i = v.length & n >0). The reason is that we check the border condition where there are no coins but still positive nominal. Probably also in return statement there should be i -1, not i+1.

Ajay Pilaniya

It can be done using 1D DP also

Asen

This coded mises few test case
amount = 250
N=24
41 34 46 9 37 32 42 21 7 13 1 24 3 43 2 23 8 45 19 30 29 18 35 11

sandeep tiwari

please use “int[][] solution = new int[v.length + 1][amount + 1];” array as long “long[][] solution = new long[v.length + 1][amount + 1];” instaed of int.

Pingback: How to show that the time complexity of algorithm is O(2^n)? - BlogoSfera()