Coin Change Problem Family Guide

Introduction

This index consolidates the major variants of the Coin Change family: minimizing coins, counting combinations, handling infinite vs finite supply, and canonical vs non-canonical denomination sets. It serves as a roadmap to choose the correct formulation, recurrence, and DP optimization.

1. Variant Taxonomy

2. Linked Problem Pages

Min Coins

Infinite Supply of Coins

Coin Change with Fewest Number of Coins Given Infinite Supply Coin Change with Fewest Number of Coins Given Canonical System and Infinite Supply

Finite Supply

Coin Change with Fewest Number of Coins Given Finite Supply

Count Number Of Ways

Infinite Supply of Coins

Coin Change - Count Number of Ways of representing Amount given Infinite Supply

Finite Supply of Coins

Coin Change - Count Number of Ways of representing Amount given Finite supply of denominations

3. Core Recurrences

Let coins[0..n-1], target A.

3.1 Counting Combinations (Infinite Supply)

Order irrelevant; outer loop over coins prevents double-counting: dp[0] = 1; For each coin c: for x = c..A: dp[x] += dp[x - c].

2D form: ways(i, a) using first i coins: ways(i, a) = ways(i-1, a) + ways(i, a - coin[i-1]) if coin[i-1] ≤ a else ways(i-1, a).

3.2 Min Coins (Infinite Supply)

dp[0] = 0; dp[x] = 1 + min_{c ≤ x}(dp[x - c]) (initialize dp with INF sentinel except 0).

3.3 Finite Supply Counting

Interpret each physical coin once (0-1 style): iterate coins outer; amounts descend for x = A..c: dp[x] += dp[x - c] to prevent reuse. If multiple coins share same denomination physically, process each as a separate 0-1 item or compress with bounded knapsack (binary split technique).

3.4 Finite Supply Min Coins

Either 2D: dp[i][a] = min(dp[i-1][a], 1 + dp[i-1][a - coin_i]) (if coin usable once) OR optimized 1D descending amounts.

3.5 Permutation Counting (Order Matters)

Reverse loop ordering: for amount from 1..A: for each coin c: if c ≤ amt: dp[amt] += dp[amt - c]. (Do NOT mix with combination loops.)

4. Canonical vs Non-Canonical Systems

Canonical (e.g., [1,5,10,25]) only guarantees greedy optimality for the Min Coin objective. For counting, the recurrence is identical; no greedy shortcut exists because counting is combinatorial, not locally optimal.

5. Complexity Summary

n = number of coin types (or total coin instances for finite), A = target amount.

6. Choosing the Right Form

7. Common Pitfalls

• Mixing loop order: outer amount + inner coins when you intended combinations (causes overcount / permutations).
• Forgetting to initialize dp[0] = 1 for counting problems (represents empty combination baseline).
• Reusing coin more than once in a finite supply variant by iterating amount ascending.
• Using greedy on non-canonical system for min coins (may be suboptimal).
• Counting permutations when combinations requested (loop order mismatch).
• Overflow (use 64-bit if combinations can exceed 32-bit range in non-LeetCode settings).

8. Relation to Other Problems

Conceptually linked to:

• Unbounded knapsack (value accumulation vs count accumulation)
• Subset sum / 0-1 knapsack (finite supply mapping)
• Partition & integer compositions (permutation counting variant)
• Rod Cutting Problem (price maximization analogous to min coins structure)
• Integer Break (maximize product; structurally similar to partition DP)

9. Edge Case Checklist

• amount = 0 → min coins = 0; count ways = 1 (empty set); permutations = 1.
• No 1-denomination coin: counting may yield 0 for unreachable amounts; min coins remains INF sentinel.
• Duplicate denominations in input → normalize by sorting & deduplicating if only types matter.
• Empty coin list → only amount=0 reachable.

10. Implementation Patterns (1D DP Skeletons)

Combinations (infinite supply):

1
2
3
4
5

dp = [0]*(A+1)
dp[0] = 1
for c in coins:
  for x in range(c, A+1):
    dp[x] += dp[x-c]

Permutations (order matters):

1
2
3
4
5
6

dp = [0]*(A+1)
dp[0] = 1
for x in range(1, A+1):
  for c in coins:
    if c <= x:
      dp[x] += dp[x-c]

Min coins (infinite):

1
2
3
4
5
6

INF = 10**9
dp = [INF]*(A+1)
dp[0] = 0
for c in coins:
  for x in range(c, A+1):
    dp[x] = min(dp[x], dp[x-c] + 1)

Finite supply (0-1) count:

1
2
3
4
5

dp = [0]*(A+1)
dp[0] = 1
for c in coins:  # each coin usable once
  for x in range(A, c-1, -1):
    dp[x] += dp[x-c]

11. When to Use 2D vs 1D

Use 2D when you need reconstruction by coin index or to differentiate coin usage counts explicitly. Use 1D for memory efficiency and pure count/min objectives where reconstruction is either not needed or can be derived by a second pass.

12. Further Extensions

• Adding a modulo (e.g., 1e9+7) for large counts.
• Weighted coin counts or limits → bounded knapsack.
• Multi-dimensional constraints (e.g., weight + amount) → multi-axis DP.

13. Quick Reference Table (Summary)