Coin Change Ways | Dataford Interview Questions

Quid's media intelligence workflows may need to count valid combinations of fixed-value analysis credits. Given an amount and a set of coin denominations, return the number of combinations that produce the amount when each denomination can be used unlimited times.

The order of coins does not matter, so [1, 2] and [2, 1] represent the same combination. Return the exact count as a Python integer.

Formal Specification

Implement count_change(amount, coins).

amount is a non-negative integer.
coins is a list of distinct positive integers.
Return an integer representing the number of order-independent combinations whose values sum to amount.
Return 1 for amount 0, because choosing no coins is one valid combination.
Return 0 when no combination exists.

Constraints

0 <= amount <= 10^4
1 <= len(coins) <= 100
1 <= coins[i] <= 10^4
All coin denominations are distinct positive integers
Each denomination may be used unlimited times
The result must be returned exactly

Function Signature

def count_change(amount, coins):

Your question is Coin Change Ways. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem