Start learning free

LESSON 456 OF 543 · DYNAMIC PROGRAMMING

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

    RUST · DYNAMIC PROGRAMMING

    Coin Change Ii in Rust, explained

    Problem overview

    The function change receives a target amount and a vector of distinct coin values, coins. It returns how many different combinations of coins add up to exactly amount, or 0 if none do. Each coin value can be used any number of times. A combination counts how many coins of each value it uses, not 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 coins of 2 only make even sums. For amount = 0 the answer is 1: the combination that uses no coins at all.

    Approach: count the ways to make every smaller sum

    Listing every combination is hopeless for large inputs, since the number of combinations grows very quickly. The lesson counts them instead. 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, the empty combination, and every other entry at 0. Then the coins are added one at a time. For a given coin, every combination for the sum a - coin, plus one more of this coin, is a combination for a. So ways[a] grows by ways[a - coin]. Going through the sums upward matters: ways[a - coin] already includes combinations that use this coin, so one coin value can be used again and again.

    The order of the two loops is what makes this count combinations and not orders. While a coin is being added, the table only contains combinations built from the coins before it. Each combination is therefore assembled in one fixed order, all its coins of the first value, then of the second, and so on, and it is counted exactly once. With the sums in the outer loop 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.

    Here is the table for amount = 5 and coins = [1, 2, 5], after each coin is added (index 0 is first):

    start   [1, 0, 0, 0, 0, 0]
coin 1  [1, 1, 1, 1, 1, 1]
coin 2  [1, 1, 2, 2, 3, 3]
coin 5  [1, 1, 2, 2, 3, 4]

    With only 1-coins, every sum has one way. Adding 2-coins gives sum 4 three ways (1+1+1+1, 2+1+1, 2+2), and adding the 5-coin gives sum 5 one more way, for a total of 4.

    Step by step

    1. Create ways as a mutable vector of amount as usize + 1 zeros. The sizes and indexes in Rust are usize, so amount is converted, and the zero is written 0i32 so the counts have the same type as the return value.
    2. Set ways[0] to 1. The sum 0 has exactly one combination, the one with no coins, and every other combination grows from it.
    3. Loop over the coins with &coins, so the vector is borrowed, and the pattern &coin, which copies each value out. The coins are the outer loop.
    4. Loop over the sums from coin up to amount, inclusive. A sum smaller than the coin can't contain it. Going upward lets a smaller sum already include this coin.
    5. Add ways[a - coin as usize] to ways[a]. This is the key line: every way to make a - coin, plus one coin, is a way to make a.
    6. Return ways[amount as usize] as the last expression, with no semicolon.

    The solution in Rust

    impl Solution {
    fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let mut ways = vec![0i32; amount as usize + 1];
        ways[0] = 1;
        for &coin in &coins {
            for a in coin as usize..=amount as usize {
                ways[a] += ways[a - coin as usize];
            }
        }
        ways[amount as usize]
    }
}

    The Rust details worth a closer look:

    • vec![0i32; n] builds a vector of n copies of the value. The i32 suffix fixes the element type.
    • Casts and precedence. as binds tighter than -, so a - coin as usize means a - (coin as usize), which is usize minus usize. The loop only reaches sums where a >= coin, so this subtraction never goes below zero.
    • The range coin as usize..=amount as usize. The ..= includes the end. When coin is larger than amount, the range is empty and the loop body never runs. That also handles amount = 0.
    • for &coin in &coins. Iterating over &coins yields &i32 references, and the pattern &coin copies the number out so coin is a plain i32.
    • Overflow. The lessons build with -O, where i32 overflow wraps silently, but the constraints promise that every count fits in 32 bits, so it doesn't happen. In a debug build the same overflow would panic.

    Complexity

    Time: O(n · amount), where n is the number of coins. Each coin makes one pass over at most amount + 1 sums, and each step is one addition.

    Space: O(amount). ways holds amount + 1 counts, and nothing else grows with the input.

    Edge cases and common mistakes

    • Swapping the loops. With the sums outside and the coins inside, amount = 4 and coins = [1, 2, 3] gives 7, not 4: it counts 3 + 1 and 1 + 3 separately. With the coins outside, the answer is 4.
    • Amount zero. change(0, vec![7]) returns 1, the empty combination. That is why ways[0] starts at 1 and not 0.
    • A coin larger than the amount. change(3, vec![5]) returns 0. The inner range is empty, so ways keeps its initial values.
    • Starting the inner loop at zero. a - coin as usize would then be below zero for small a. In Rust that is an overflow panic in a debug build and a wrapped, enormous index in a release build, which panics on the vector access.
    • Going downward in the inner loop. Counting sums from amount down to coin lets each coin be used at most once, which solves a different problem. For amount = 5 and coins = [1, 2, 5] it would not count 2 + 2 + 1.

    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 = 3, coins = [5] gives 0.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free