# LeetCode 518: Coin Change II

## Problem Restatement

We are given an integer `amount` and an array `coins`.

Each value in `coins` is a coin denomination.

We have an infinite number of each coin type.

We need to return the number of different combinations that can make up exactly `amount`.

If the amount cannot be formed, return `0`.

The order of coins does not matter. For example, `[1, 2, 2]` and `[2, 1, 2]` represent the same combination.

The official problem asks for the number of combinations that make up the amount, with unlimited coins of each denomination. The answer is guaranteed to fit in a signed 32-bit integer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `amount` and integer array `coins` |
| Output | Number of combinations |
| Coin supply | Unlimited copies of each coin |
| Order | Does not matter |
| Impossible case | Return `0` |

Function shape:

```python
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        ...
```

## Examples

Example 1:

```python
amount = 5
coins = [1, 2, 5]
```

The combinations are:

```text
5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
```

So the answer is:

```python
4
```

Example 2:

```python
amount = 3
coins = [2]
```

Using only coin `2`, we cannot form `3`.

So the answer is:

```python
0
```

Example 3:

```python
amount = 10
coins = [10]
```

There is exactly one way:

```text
10
```

So the answer is:

```python
1
```

## First Thought: Try All Choices

For each coin, we can choose:

1. Use it.
2. Skip it.

Since each coin can be used unlimited times, using a coin does not move us to the next coin. We may use it again.

A recursive state could be:

```text
dfs(index, remaining)
```

where `index` is the current coin type and `remaining` is the amount left.

The choices are:

```text
use coins[index]
skip coins[index]
```

This works conceptually, but without memoization it recomputes many states.

## Problem With Plain Recursion

The same remaining amount can be reached in many ways.

For example, with:

```python
coins = [1, 2, 5]
amount = 5
```

the state "make amount `3` using coins `[1, 2, 5]`" can appear through several recursive paths.

This overlapping work suggests dynamic programming.

## Key Insight

We need to count combinations, not permutations.

That means the order of using coins must be fixed.

If we process coins one by one, then each combination is counted exactly once.

For each coin, update the number of ways to form each amount.

Let:

```text
dp[x]
```

mean:

```text
the number of combinations that form amount x using the coins processed so far
```

Initialize:

```python
dp[0] = 1
```

There is one way to make amount `0`: choose no coins.

For each coin, we scan amounts from `coin` up to `amount`.

When processing coin `c`, the transition is:

```text
dp[x] += dp[x - c]
```

This means every way to form `x - c` can be extended by adding one coin `c`.

## Algorithm

Create a DP array of length `amount + 1`.

Initialize:

```python
dp[0] = 1
```

Then for each coin `c` in `coins`:

1. For every value `x` from `c` to `amount`
2. Add `dp[x - c]` into `dp[x]`

Finally, return:

```python
dp[amount]
```

The loop order is important.

Coins are the outer loop.

Amounts go forward in the inner loop.

This allows unlimited use of the current coin while preventing different orders of the same combination from being counted multiple times.

## Correctness

After processing some prefix of the coin list, `dp[x]` stores the number of combinations that form amount `x` using only those processed coins.

Initially, before any real coin is processed, `dp[0] = 1` because there is exactly one way to form amount `0`: use no coins. Every positive amount has zero ways.

When processing coin `c`, for each amount `x >= c`, every existing combination that forms `x - c` can be extended by adding one coin `c`. Since the inner loop moves forward, `dp[x - c]` already includes combinations that may use coin `c` multiple times.

Adding `dp[x - c]` to `dp[x]` therefore counts exactly the combinations for amount `x` that use at least one coin `c`.

Combinations that do not use coin `c` were already present in `dp[x]`.

Because coins are processed in a fixed order, the same multiset of coins is counted once, not once per ordering.

After all coins are processed, `dp[amount]` is exactly the number of combinations that form `amount`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * amount)` | For each coin, we scan amounts up to `amount` |
| Space | `O(amount)` | The DP array stores one value per amount |

Here, `n = len(coins)`.

## Implementation

```python
from typing import List

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for value in range(coin, amount + 1):
                dp[value] += dp[value - coin]

        return dp[amount]
```

## Code Explanation

Create the DP array:

```python
dp = [0] * (amount + 1)
```

Set the base case:

```python
dp[0] = 1
```

This represents using no coins.

Process one coin type at a time:

```python
for coin in coins:
```

For each amount that can use this coin:

```python
for value in range(coin, amount + 1):
```

add the number of ways to form the remaining amount:

```python
dp[value] += dp[value - coin]
```

At the end:

```python
return dp[amount]
```

returns the number of combinations for the target amount.

## Testing

```python
def test_change():
    s = Solution()

    assert s.change(5, [1, 2, 5]) == 4
    assert s.change(3, [2]) == 0
    assert s.change(10, [10]) == 1
    assert s.change(0, [1, 2, 5]) == 1
    assert s.change(4, [1, 2]) == 3
    assert s.change(5, [5, 1, 2]) == 4

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| `5`, `[1, 2, 5]` | Standard multi-coin case |
| `3`, `[2]` | Impossible amount |
| `10`, `[10]` | Single exact coin |
| `0`, `[1, 2, 5]` | Empty combination base case |
| `4`, `[1, 2]` | Checks repeated coin use |
| Unsorted coins | Confirms coin order does not affect the count |