518. Coin Change II

Description of Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
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: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values of coins are unique.
  • 0 <= amount <= 5000

Solution

Tags: Dynamic Programming

Explanation

Binary Selection Method

If the amount is a positive number and the number of coins available is not zero, then there are two disjoint cases: to use the current coin and not to use it. (see the following equations)

\[ w(coins, sum) = \begin{cases} 0 & \text{if } sum \lt 0 \\ 1 & \text{if } sum = 0 \\ 0 & \text{if } sum \gt 0 \land coins = \varnothing \\ w(coins, sum - c) + w(coins \setminus \{ c \} , sum) & \text{otherwise; for some c in coins} \end{cases} \]

Dynamic Programming using less space

We can also use less space. If we rewrite the recursive equation, you will get the update equation of 1-D DP table.

(coin_idx indicates that coins[0] to coins[coin_indx] are avaiable coins and coins[coin_indx] is the current selection.)

\[ w(coin\_idx, sum) = w(coins, sum - coins[ coin\_idx ]) + w(coin\_idx - 1 , sum) \] \[ \Longleftrightarrow w(sum)^{(t)} = w(sum - coins[ t ])^{(t)} + w(sum)^{(t - 1)} \]

Code (Rust)

impl Solution {
    pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let m = amount as usize;
        let n = coins.len();

        let mut dp = vec![ vec![0; m+1]; n ];

        // If it is divisible by the smallest coin
        for (j,x) in (0..=amount).enumerate() {
            dp[0][j] = if x % coins[0] == 0 {1} else {0};
        }

        // Use the equations
        for i in 1..n {
            for j in 0..=m {
                let c = coins[i] as usize;
                dp[i][j] = 
                    if j >= c { dp[i][j-c] } else {0}
                    + if i > 0 { dp[i-1][j] } else {0}
            }
        }

        dp[n-1][m]
    }
}

Code (Rust) - With less Space

impl Solution {
    pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let m = amount as usize;
        let n = coins.len();

        let mut dp = vec![ 0; m+1 ];

        dp[0] = 1;

        for i in 0..n {
            for j in 1..=m {
                let c = coins[i] as usize;
                dp[j] += if j >= c { dp[j-c] } else {0}
            }
        }

        dp[m]
    }
}

Complexity (m is the amount and n is number of coins)

Time complexity:

  • \(O(mn)\)

Auxiliary Space:

  • \( O(m) \)

Further Discussion