Coin Change II

Medium

The problem

You have unlimited coins of each value in coins. Return how many different combinations of coins add up to exactly amount. Two combinations are the same if they use the same coins in different order, so 1+2 and 2+1 count once.

Example 1
Input: amount = 5, coins = [1, 2, 5]
Output: 4
5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.
Example 2
Input: amount = 3, coins = [2]
Output: 0
Coins of 2 cannot make 3.
Example 3
Input: amount = 10, coins = [10]
Output: 1

Limits

1 ≤ len(coins) ≤ 300
1 ≤ coins[i] ≤ 5,000, all different
0 ≤ amount ≤ 5,000
The answer fits in a 32-bit integer

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You count combinations, not orderings. Process one coin type at a time.

The idea

ways[0]=1; for each coin, for a from coin to amount: ways[a] += ways[a−coin].

Target: O(amount · coins) time, O(amount) space

Go function shape

func change(amount int, coins []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// Change: number of COMBINATIONS of coins that make amount.
// Coins are the OUTER loop, so each combination is counted once, in a fixed coin order.
func Change(amount int, coins []int) int {
	ways := make([]int, amount+1)
	ways[0] = 1
	for _, coin := range coins {
		for a := coin; a <= amount; a++ {
			ways[a] += ways[a-coin]
		}
	}
	return ways[amount]
}

Read the lesson: 2-D Dynamic Programming