Coin Change Ways Count

Problem

Given unlimited coins of the listed denominations, count the number of combinations that sum to amount, where order does not matter.

Process one coin at a time and sweep amounts upward so each coin can be reused, accumulating dp[x] += dp[x - coin]. An amount of 0 has exactly one combination: the empty one.

Hint

Outer loop over coins (not amounts) prevents counting different orders as distinct.

Test cases

case 1

in: [[1,2,5],5]

expected: 4

case 2

in: [[2],3]

expected: 0

case 3

in: [[1],0]

expected: 1

case 4

in: [[1,2,3],4]

expected: 4

case 5

in: [[],0]

expected: 1

Starter codePython

def coin_change_ways(coins, amount):
    # Your code here
    pass

5 test cases · run your code against them in the editor