# Coin Change II

- **Canonical ID**: `coin-change-ii`
- **Canonical URL**: https://dsacheatsheet.com/problems/coin-change-ii
- **Difficulty**: medium
- **Patterns**: 2D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/coin-change-ii/

## 1. Core Invariant / The Trick

To count **combinations** (order-independent, `[1,2]` == `[2,1]`), place the **coin loop on the outside** and `amount` loop on the inside (`dp[a] += dp[a - c]`). Putting `amount` outside counts *permutations* instead.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(A * C)`
- **Space Complexity**: `O(A)`
- **Proof**: Processing each coin denomination completely before unlocking the next enforces canonical non-decreasing coin order inside every combination.

## 3. Minimal Idiomatic Code

### Python
```python
def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]
```

### TypeScript
```typescript
export function change(amount: number, coins: number[]): number {
  const dp = new Int32Array(amount + 1);
  dp[0] = 1;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) dp[a] += dp[a - c];
  }
  return dp[amount];
}
```

### C++
```cpp
int change(int amount, vector<int>& coins) {
    vector<unsigned long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)
        for (int a = c; a <= amount; ++a) dp[a] += dp[a - c];
    return dp[amount];
}
```

### Java
```java
int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int c : coins)
        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
    return dp[amount];
}
```

### Go
```go
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for _, c := range coins {
        for a := c; a <= amount; a++ { dp[a] += dp[a-c] }
    }
    return dp[amount]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Swapping loop order (`for a in range... for c in coins`) double-counts `[1,2]` and `[2,1]` as distinct ways!

### Follow-ups
- Combination Sum IV explicitly wants ordered permutations and swaps the loop order (`amount` outer, `nums` inner).