Start learning free

LESSON 452 OF 539 · DYNAMIC PROGRAMMING

Coin Change II in C#: O(n · amount) Dynamic Programming

Practice O(n · amount) Read the full explanation

You are given an integer amount, a total sum of money, and an array coins of different coin values.

Return the number of combinations of coins that add up to exactly amount. If no combination of the coins adds up to amount, return 0.

You may use each coin value as many times as you want. A combination counts how many coins of each value it uses, not their order: 2 + 2 + 1 and 1 + 2 + 2 are the same combination.

 

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: There are four combinations:
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: Coins of 2 only make even sums, so 3 can't be made.

Example 3:

Input: amount = 4, coins = [1, 2, 3]
Output: 4
Explanation: 4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 2 + 2 = 3 + 1. Counting different orders as different, such as 3 + 1 and 1 + 3, would give 7 instead.

 

Constraints:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values in coins are different.
  • 0 <= amount <= 5000 (when amount is 0, the answer is 1: the combination of no coins at all)
  • The answer fits in a 32-bit signed integer, and so does the number of combinations for every smaller amount.

Note:

Your algorithm should run in O(n · amount) time and O(amount) space, where n is the number of coins.



Listing every combination is far too slow: a few dozen coins can make more than a billion combinations of 5000. Count them instead: let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. Start with ways[0] = 1, the combination of no coins, and every other entry at 0. The answer is ways[amount].

Add the coins one at a time, in an outer loop. For each coin, go over the sums a from coin up to amount and add ways[a - coin] to ways[a]: every combination for a - coin, plus one more of this coin, is a combination for a. Going up lets ways[a - coin] already contain this coin, so it can be used many times.
Why the coins must be the outer loop: when a coin is added, the counts so far only use the coins before it. So every combination is built in one fixed order, first all its coins of the first value, then all of the second, and so on, and it is counted exactly once: 1 + 3 is counted, 3 + 1 never is. With the sums outside and the coins inside, any coin could be the last one added to any sum, so 1 + 3 and 3 + 1 would both be counted: that counts orders, not combinations.

Each of the n coins goes over at most amount + 1 sums, with a constant amount of work for each: O(n · amount) time. ways holds amount + 1 counts: O(amount) space.
STEP 1 OF 6
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Coin Change Ii in C#, explained

    Problem overview

    The method Change receives a target amount and an array coins of distinct coin values. It returns how many different combinations of coins add up to exactly amount, or 0 if there are none. Each coin value can be used any number of times. A combination is defined by how many coins of each value it uses, not by their order, so 2 + 2 + 1 and 1 + 2 + 2 are the same combination.

    For amount = 5 and coins = {1, 2, 5} the answer is 4: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1. For amount = 3 and coins = {2} the answer is 0, since 2s only make even sums. When amount is 0 the answer is 1: the empty combination.

    The lesson asks for O(n · amount) time and O(amount) space, where n is the number of coins.

    Approach: count the ways for every smaller sum

    Listing combinations one by one is hopeless: a few dozen coin values can already produce over a billion combinations of 5000. Instead, count them. Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. The answer is ways[amount].

    The table starts with ways[0] = 1 (no coins, sum 0) and zeros everywhere else, because with no coins available no positive sum can be made. Then the coins are added one at a time. When a coin is added, every combination for a - coin, plus one more of this coin, is a combination for a. So ways[a] grows by ways[a - coin].

    Two choices in that loop decide the result:

    • Sums go upward. While handling a coin, ways[a - coin] has already been updated for the same coin, so it may contain that coin once or more. This is what lets one coin value be used again and again.
    • Coins are the outer loop. When a coin is added, the table only knows combinations built from the coins before it. Each combination is therefore built in one fixed order: all its coins of the first value, then of the second, and so on. It is counted exactly once. 1 + 3 is counted and 3 + 1 never is.

    Swapping the loops, with the sums outside and the coins inside, counts orders instead of combinations. For amount = 4 and coins = {1, 2, 3} the correct loop order returns 4, and the swapped one returns 7, because it counts 3 + 1 and 1 + 3 separately.

    The table, coin by coin

    For amount = 5 and coins = {1, 2, 5}, these are the contents of ways (indices 0 to 5) after each coin:

    after coin 1: 1 1 1 1 1 1
after coin 2: 1 1 2 2 3 3
after coin 5: 1 1 2 2 3 4

    After the coin 1, every sum has one way: all ones. After the coin 2, the sum 4 has three ways (1+1+1+1, 2+1+1, 2+2) and 5 has three. After the coin 5, the sum 5 gains the single-coin combination, giving 4.

    Step by step

    1. Create ways, an int[] of size amount + 1, so that index amount exists. A new int array is filled with zeros.
    2. Set ways[0] to 1. The sum 0 has exactly one combination, the empty one, and every other count grows from it.
    3. Loop over the coins with foreach (int coin in coins). This is the outer loop, which makes the counts combinations.
    4. Loop over the sums from coin up to and including amount. A sum smaller than the coin can't contain it, and going upward allows repeated use.
    5. Add ways[a - coin] to ways[a] with +=. This line is the whole dynamic programming idea: each entry reuses the counts for smaller sums.
    6. Return ways[amount] after the loops. When amount is 0 the inner loop never runs, and this returns ways[0], which is 1.

    The solution in C#

    class Solution {
    public int Change(int amount, int[] coins) {
        int[] ways = new int[amount + 1];
        ways[0] = 1;
        foreach (int coin in coins) {
            for (int a = coin; a <= amount; a++) {
                ways[a] += ways[a - coin];
            }
        }
        return ways[amount];
    }
}

    The C# details worth knowing:

    • Array defaults. new int[amount + 1] gives zeros, so only ways[0] needs setting. Arrays have a fixed length, which is why the size is amount + 1.
    • foreach and for. foreach reads each coin without an index. The inner loop needs a start and an end that depend on coin, so it is a plain for.
    • int overflow. Counts are 32-bit and wrap silently in C#'s default unchecked arithmetic. The lesson's constraints promise that every count fits, so the code doesn't guard against it.
    • Compound assignment. ways[a] += ways[a - coin] reads and writes the same array in one statement. The index a - coin is never negative because the loop starts at a = coin.

    Complexity

    Time: O(n · amount). Each of the n coins is handled by a loop of at most amount + 1 iterations, each doing one addition. For coins = {1, 2, 5} and amount = 5000 the method returns 1252001 almost instantly.

    Space: O(amount). The only extra memory is ways, with amount + 1 integers.

    Edge cases and common mistakes

    • Amount 0. The answer is 1, from the empty combination. For amount = 0 and coins = {7} the method returns 1.
    • A coin larger than the amount. The inner loop starts above amount and doesn't run, so the coin is ignored. amount = 3 with coins = {2} returns 0.
    • A coin equal to the amount. amount = 10 with coins = {10} returns 1.
    • Swapped loops. This counts orders and returns 7 instead of 4 for the third example. Coins must be outside.
    • Looping downward. Going from amount down to coin would let each coin be used at most once, which solves a different problem. Here the direction must be upward.
    • Starting ways[0] at 0. Every count would stay 0, since all counts grow from the empty combination.
    • Coin order. The result does not depend on the order of coins: {5, 2, 1} with amount 5 also returns 4.

    Testing

    • amount = 5, coins = {1, 2, 5} gives 4.
    • amount = 3, coins = {2} gives 0.
    • amount = 4, coins = {1, 2, 3} gives 4.
    • amount = 0, coins = {7} gives 1.
    • amount = 10, coins = {10} gives 1.
    • amount = 5000, coins = {1} gives 1.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free