Number Of Ways To Make Change

Tags

Number Of Ways To Make Change

Category

Dynamic Programming

Difficulty

Medium

Problem Statement

Given a target amount n and an array of positive integer coin denominations, return the number of distinct ways to make change for the target amount. Each denomination can be used an unlimited number of times.

Intuition

This is a classic unbounded knapsack / coin change counting problem. We build a DP table where dp[amount] represents the number of ways to make change for that amount. By processing one denomination at a time and updating the table, we ensure that each combination is counted exactly once (avoiding permutation duplicates). The order in which we iterate over denominations eliminates duplicate counting because {1,2} and {2,1} are the same combination.

Approach

  1. Create an array dp of size n + 1, initialized to 0.
  2. Set dp[0] = 1 (there is one way to make 0: use no coins).
  3. For each denomination coin in the denominations array:
    • For each amount from coin to n:
      • dp[amount] += dp[amount - coin]
  4. Return dp[n].

Pseudocode

function numberOfWaysToMakeChange(n, denominations):
    dp = array of size (n + 1) filled with 0
    dp[0] = 1

    for coin in denominations:
        for amount from coin to n:
            dp[amount] += dp[amount - coin]

    return dp[n]

Time & Space Complexity

  • Time: O(n * d) where n is the target amount and d is the number of denominations.
  • Space: O(n) for the DP array.

Key Insights

  • Iterating denominations in the outer loop and amounts in the inner loop counts combinations (not permutations). If the loops were swapped, we would count permutations.
  • dp[0] = 1 is the crucial base case: there is exactly one way to make 0 change (use no coins).
  • Each denomination can be used unlimited times because the inner loop starts at coin (not at n - coin going backward).
  • If no combination of coins sums to n, dp[n] remains 0.

Edge Cases

  • Target amount is 0: return 1 (one way — use no coins).
  • No denominations available: return 0 for any positive target (no way to make change).
  • Single denomination that does not divide n evenly: return 0.
  • Denomination of 1 is in the array: there is always at least one way to make change.
  • Very large target amounts may require careful consideration of integer overflow.

Linked mentions