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:

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.

1. Solutions that do not contain ith coin (or coins[i]).
2. 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.

### 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.

The space optimized version:

0%