Coin Change

1. 1.Coin Change — Minimum Coins
   Unbounded min coins DP: dp[a] = min(dp[a], 1 + dp[a-coin]) with INF basemedium
2. 2.Coin Change II — Number of Combinations
   Unbounded combinations DP: outer coin loop, inner amount left-to-rightmedium
3. 3.Combination Sum IV — Ordered Ways
   Unbounded permutations DP: outer amount loop, inner coin loopmedium
4. 4.Perfect Squares
   Unbounded min items DP: coins are perfect squares 1, 4, 9...medium
5. 5.Minimum Cost to Fill Exact Weight
   Unbounded min cost DP with exact weight capacity targetmedium
6. 6.Minimum Coins With Given Denominations
   Base Coin Change min coins DP initialized with INFmedium
7. 7.Count Ways to Make an Amount
   Unbounded combination counting DPmedium
8. 8.Rod Cutting — Unbounded Knapsack relation
   Unbounded max profit DP: piece length = weight, selling price = valuemedium
9. 9.Integer Break — related reusable-choice DP
   Unbounded product maximization DP for integer split partsmedium
10. 10.Minimum Number of Coins to Reach Target
    Min coins DP returning -1 if dp[target] == INFmedium

1. 11.Coin Change With Limited Coins
   Bounded Knapsack DP with coin count limits (binary splitting)medium
2. 12.Return Actual Coins Used
   Track choice[a] pointers during DP fill to reconstruct optimal coin listmedium
3. 13.Coin Change With Impossible Amounts
   Detecting unreachable amounts where dp[target] remains INFmedium
4. 14.Coin Change With Large Target
   Analyzing constraint scaling when amount = 10^9hard
5. 15.Canonical Coin Systems / Greedy vs DP
   Proof of why Greedy fails on arbitrary coin systems (e.g. [1, 3, 4] for amount 6)medium
6. 16.Count Ordered vs Unordered Ways
   Loop order comparison: outer coin (unordered) vs outer amount (ordered)medium
7. 17.Bounded Coin Change — advanced
   Deque / Sliding window max optimization for bounded coin quantitieshard
8. 18.Coin Change Using BFS — alternative view
   Shortest path BFS tree over amount states when all edges cost 1 movemedium

1. Coins reusable unlimited times?Unbounded Knapsack
2. Need minimum number of coins?dp[amount] = min coins (dp[0]=0, others INF)
3. Need number of combinations?Coin Change II (Outer coin loop)
4. Need order to matter (permutations)?Combination Sum IV (Outer amount loop)
5. Is largest coin first always optimal?NO! Greedy fails on arbitrary coin systems

package main

import "fmt"

// Coin Change Min Coins: O(Amount * Coins) time, O(Amount) space
func coinChange(coins []int, amount int) int {
    const inf = 1e9
    dp := make([]int, amount+1)
    for a := 1; a <= amount; a++ {
        dp[a] = inf // Initialize unreachable amounts to INF
    }
    dp[0] = 0 // Base case: amount 0 needs 0 coins

    for a := 1; a <= amount; a++ {
        for _, coin := range coins {
            if coin <= a && dp[a-coin] != inf {
                if 1+dp[a-coin] < dp[a] {
                    dp[a] = 1 + dp[a-coin]
                }
            }
        }
    }
    if dp[amount] == inf {
        return -1
    }
    return dp[amount]
}

// Coin Change II Combinations Count: Outer Coin Loop
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1 // Base case: 1 way to make amount 0 (empty set)

    for _, coin := range coins {
        for a := coin; a <= amount; a++ {
            dp[a] += dp[a-coin]
        }
    }
    return dp[amount]
}

func main() {
    coins := []int{1, 3, 4}
    amount := 6

    fmt.Println("Min Coins:", coinChange(coins, amount)) // Output: 2 (Coins: 3+3)
    fmt.Println("Combinations Count:", change(5, []int{1, 2, 5})) // Output: 4
}

Core Coin Mechanics & Greedy Failure Proof

Coin Change Goal -> Minimum Coins to reach Target Amount
Base Case -> dp[0] = 0; All other amounts = INF
Transition -> dp[a] = min(dp[a], 1 + dp[a - coin])
Greedy Failure -> [1, 3, 4] for amount 6 -> Greedy yields 3 coins (4+1+1) vs DP yields 2 coins (3+3)
Combinations Count (Coin Change II) -> for coin in coins { for amount in coin..W }
Permutations Count (Combination Sum IV) -> for amount in 1..W { for coin in coins }

Coin Change Variants & Shortest-Path BFS View

Common Interview Mistakes

• • Assuming Greedy (picking largest coin first) is always optimal for arbitrary coin systems.
• • Initializing positive amounts to 0 for minimum coins DP instead of infinity (INF).
• • Forgetting base case initialization dp[0] = 0, causing all amounts to evaluate as unreachable.
• • Adding 1 to INF (dp[a-coin] + 1) without checking if dp[a-coin] == INF, causing integer overflow.
• • Treating coin denominations as 0/1 items (single use) instead of Unbounded items (unlimited reuse).
• • Swapping loop order in Coin Change II (accidentally counting permutations instead of combinations).
• • Failing to return -1 when dp[target] remains INF (unreachable target amount).
• • Attempting 1D capacity DP when target amount = 10^9 without checking constraint bounds (Memory Limit Exceeded).
• • Confusing Coin Change (min coins DP) with Coin Change II (combinations count DP).

Interview Rules

Reusable coins + target amount? → Coin Change (Unbounded Knapsack)
Rule 1                           → Define dp[a] = min coins to make amount a
Rule 2                           → Base Case: dp[0] = 0; All other amounts = INF
Rule 3                           → Transition: dp[a] = min(dp[a], 1 + dp[a-coin])
Rule 4                           → Return -1 if dp[target] == INF
Rule 5                           → Coin Change II = Outer coin loop; Combination Sum IV = Outer amount loop
Rule 6                           → Greedy fails on non-canonical coins (e.g. [1, 3, 4] for amount 6)
Time Complexity                  → O(Amount * Coins)
Space Complexity                 → O(Amount) 1D Array

💡 Golden Rule: For every amount, try using each reusable coin once now, then add one to the best answer already known for the remaining amount.

Coin Change Goal: Minimum coins to reach amount
Base Case: dp[0] = 0, others INF
Transition: dp[a] = min(dp[a], 1 + dp[a-coin])
Greedy Failure: [1, 3, 4] for amount 6 -> DP gives 2 (3+3) vs Greedy gives 3 (4+1+1)
Unreachable Target: return -1 if dp[target] == INF
Combinations Count: for coin { for amount }
Permutations Count: for amount { for coin }