You are given an integer array

`coins`

representing coins of different denominations and an integer`amount`

representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return `-1`

.

You may assume that you have an infinite number of each kind of coin.

Example 1: Input: coins = [1,2], amount = 4 Output: 2 Explanation: 4 =

2 + 2,4=1+1+2

## The recursion formual for coin change as below

$coinchange(j,a) = \begin{cases} \infty, & \text{if $j$<0} \\ 0, & \text{if $j$ =0} \\ 1+\min(\sum_{i=k}^n c[j-a_i]) & \text{if $j$ >1} \end{cases}$

```
function coin_change(amount) {
// if remaining coin is zero return
if (amount == 0) return 0
// if coin is negative return some large value
if (amount < 0) return Infinity
let ans = Infinity
for (const coin of coins)
ans = Math.min(
ans,
1 + coin_change(amount - coin)
)
return ans
}
```

## Recursion Tree

This article only show you how to write recursive program. I know this is not optimized way to write coin change problem{alertError}