Start learning free

LESSON 453 OF 540 · DYNAMIC PROGRAMMING

Coin Change II in Kotlin: 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

    KOTLIN · DYNAMIC PROGRAMMING

    Coin Change Ii in Kotlin, explained

    Problem overview

    Given a target amount and an IntArray of distinct coin values coins, change returns how many different combinations of coins add up to exactly amount. 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, because 2s only make even sums. For amount = 0 the answer is 1: the combination that uses no coins at all.

    Approach

    Listing every combination is hopeless: with a few dozen coins and an amount of 5000, the count can pass a billion. The way out is to count instead of list.

    Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. The array starts with ways[0] = 1 (no coins make 0) and zeros elsewhere. The answer is ways[amount].

    Now add the coins 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]. Looping a upwards means ways[a - coin] may already include this coin, which is exactly how one coin value gets used many times.

    Why the coins are the outer loop

    This choice decides whether you count combinations or orderings. While a coin is being added, the counts so far use only the coins before it in the array. So each combination is built in one fixed order: all its coins of the first value, then all of the second, and so on. It is counted exactly once. 1 + 3 is counted when the 3 is added to a sum that already holds a 1, and 3 + 1 is never built.

    Swap the loops (sums outside, coins inside) and any coin can be the last one added to any sum, so 1 + 3 and 3 + 1 are both counted. That counts orderings. With amount = 4 and coins = [1, 2, 3], the lesson's loop order returns 4 (1+1+1+1, 2+1+1, 2+2, 3+1) and the swapped version returns 7. With amount = 5 and coins = [1, 2, 5] the swapped version returns 9 instead of 4.

    Step by step

    1. Make the table. val ways = IntArray(amount + 1). A new IntArray is filled with zeros, and the extra slot is for the sum 0. val keeps the name on the same array while its entries still change.
    2. Seed it. ways[0] = 1. Every other count grows out of this one combination of no coins.
    3. Loop over the coins. The outer for (coin in coins) adds one coin value at a time.
    4. Loop over the sums. The inner loop runs a over coin..amount. Sums below coin cannot contain it. The range .. includes amount, and when coin is larger than amount the range is empty, so that coin does nothing.
    5. The key line. ways[a] += ways[a - coin] adds every combination for a - coin, extended by one coin.
    6. Return ways[amount].

    The solution in Kotlin

    class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val ways = IntArray(amount + 1)
        ways[0] = 1
        for (coin in coins) {
            for (a in coin..amount) {
                ways[a] += ways[a - coin]
            }
        }
        return ways[amount]
    }
}

    Kotlin details worth knowing:

    • Ranges are inclusive. coin..amount includes both ends. If you wrote coin until amount, the last sum, amount itself, would never be filled.
    • Empty ranges are fine. When coin > amount, the loop body never runs, so you do not need an if.
    • Int wraps silently. A sum that passes 2147483647 wraps to a negative number with no error. The constraints promise that the answer and the count for every smaller amount fit in an Int, so IntArray is safe here.
    • ways[a] += ... works on array elements. It reads the element, adds, and writes it back.

    Tracing an example

    For amount = 5 and coins = [1, 2, 5], this is ways (indexes 0 to 5) at the start and after each coin:

    start:        [1, 0, 0, 0, 0, 0]
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]

    With only 1s, each sum has one combination. Adding 2s gives sum 4 three combinations (1+1+1+1, 2+1+1, 2+2), and the coin 5 adds the combination 5 to sum 5, for 4 in total.

    Complexity

    Time: each of the n coins walks over at most amount + 1 sums, with constant work per sum: O(n · amount). With 300 coins and an amount of 5000, that is about 1.5 million steps.

    Space: ways has amount + 1 entries: O(amount).

    Edge cases and common mistakes

    • Amount 0. The loops do nothing and the function returns ways[0], which is 1. change(0, intArrayOf(7)) returns 1.
    • Amount that cannot be made. change(3, intArrayOf(5)) returns 0, and so does the 3 with a single 2 coin.
    • Swapped loops. This is the classic mistake, and the tests with amount = 4 or 5 show it as 7 or 9 instead of 4.
    • Starting ways[0] at 0. Then every entry stays 0, since all counts grow from that one seed.
    • Looping a downwards. A downward loop lets each coin be used at most once, which solves a different problem.

    Testing

    The example inputs return these results:

    change(5, [1, 2, 5]) = 4
change(3, [2])       = 0
change(4, [1, 2, 3]) = 4
change(0, [7])       = 1
change(3, [5])       = 0
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free