Write a function that counts how many different ways you can make change for an amount of money, given an array of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2:

1 | 1+1+1+1, 1+1+2, 2+2. |

The order of coins does not matter. Also, assume that you have an infinite amount of coins.

## Solution

### Recursion

#### Optimal Substructure

To count total number solutions, we can divide all set solutions in two sets.

- Solutions that do not contain ith coin (or coins[i]).
- Solutinos that contain at least one coins[i].

Let `count(coins[], money, index)`

be the function to count the number of solutions, then it can be written as sum of `count(coins[], money, index)`

and `count(coins[], money - coins[index], index)`

.

#### Overlapping Subproblems and Implementation

Following is a simple recursive implementation of the Coin Change problem. The implementation simply follows the recursive structure mentioned above.

1 | var countChange = function(coins, money, index = coins.length - 1) { |

### Dynamic Programming

Since same subproblems are called ageain, this problem has Overlapping Subprolems property. So the Coin Change problem has both properties of a dynamic programming problem. Like other typical DP problems, recomputations of same subproblems can be avoided by constructing a temporary array dp[][] in bottom up manner.

1 | var countChange = function(coins, money) { |

The space optimized version:

1 | var countChange = function(coins, money) { |