518. Coin Change II #

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

Problem Summary #

You are given an integer array coins representing coins of different denominations, and another integer amount representing the total amount. Calculate and return the number of coin combinations that can make up the total amount. If no combination of coins can make up the total amount, return 0. Assume that you have an infinite number of each denomination of coin. The test data guarantees that the result fits into a 32-bit signed integer.

Solution Ideas #

• Although this problem is called Coin Change, it is not the classic “Nine Lectures on Knapsack” problem. Each element in coins can be chosen multiple times, and the order of the chosen elements is not considered, so what this problem actually requires is calculating the number of combinations for selecting coins. Define dp[i] as the number of coin combinations whose sum is equal to i; the goal is to find dp[amount]. The initial boundary condition is dp[0] = 1, meaning that choosing no coins is one way, and the amount is 0. The state transition equation is dp[i] += dp[i-coin], where coin is the currently enumerated coin.
• Some readers may wonder whether the above approach will cause duplicate counting. The answer is no. The outer loop iterates over the values in the array coins, and the inner loop iterates over different amount sums. When calculating the value of dp[i], it ensures a fixed order for the coin denominations whose sum is equal to i; since the order is fixed, different permutations will not be counted repeatedly.
• Problems with exactly the same solution idea as this one include Problem 377 and Problem 494.

Code #

package leetcode

func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] += dp[i-coin]
		}
	}
	return dp[amount]
}