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

Dimension	Options	Meaning / Effect
Objective	Min Coins / Count Ways / Enumerate Solutions / Check Feasibility	Different DP state meanings & transitions
Supply	Infinite (Unbounded) / Finite (Bounded)	Infinite → unbounded knapsack style reuse; Finite → 0-1 per coin instance or quantity-limited loop
Order Relevance	Combinations (order irrelevant) / Permutations (order matters)	Changes loop ordering or recurrence orientation
Denomination System	Canonical / Non-Canonical	Only affects existence of greedy for Min Coins; does NOT change counting DP
Space Optimization	2D DP / 1D Rolling	1D safe only when using combination ordering (outer coins, inner amounts ascending)

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-infinite-supply) [Coin Change with Fewest Number of Coins Given Canonical System and 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](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](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](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

Variant	Standard DP Time	Space (2D)	Space (Optimized)	Notes
Min Coins (Infinite)	O(n * A)	O(n * A)	O(A)	Unbounded knapsack style
Min Coins (Finite)	O(n * A)	O(n * A)	O(A) (desc loop)	0-1 knapsack style
Count Ways (Infinite Combos)	O(n * A)	O(n * A)	O(A)	Outer coins ascending amounts
Count Ways (Finite)	O(n * A)	O(n * A)	O(A)	Amounts descend to prevent reuse
Permutation Count	O(n * A)	O(A)	O(A)	Loop order flips (amount outer)

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

6. Choosing the Right Form

Question	Use
“Fewest coins?”	Min Coins DP; consider greedy only if system known canonical
“How many combinations?”	Combination counting DP (outer coins)
“How many sequences (order matters)?”	Permutation DP (outer amount)
“Each coin once?”	0-1 / finite supply variant with descending amount loop
“Large denomination counts?”	Bounded knapsack via binary splitting of counts

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](rod-cutting-problem) (price maximization analogous to min coins structure)
• [Integer Break](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):

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):

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):

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:

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)

Goal	Outer Loop	Inner Loop	Overcount Risk	Space Optimizable?
Count combinations (∞)	coins	amount ↑	No (if sorted/unique)	Yes (1D)
Count permutations (∞)	amount ↑	coins	N/A (intended)	Yes
Min coins (∞)	coins	amount ↑	N/A	Yes
Count combinations (finite)	coins	amount ↓	If amount ↑ → reuse bug	Yes
Min coins (finite)	coins	amount ↓	If amount ↑ → reuse bug	Yes