Let S be a finite set of positive numbers. The problem we want to solve is to find out the number of distinct ways for a given integer x to be expressed as the sum of multiples of the positive numbers chosen from S. If we interpret each number in S as the denomination of a coin, then the problem asks how many distinct ways there exist for a given value x to be expressed as the sum of a set of coins. If we use cc(S, x) for this number, then we have the following properties on the function cc:
cc(S, 0) = 1 for any S.
If x < 0, then cc(S, x) = 0 for any S.
If S is empty and x > 0, then cc(S, x) = 0.
If S contains a number c, then cc(S, x) = cc(S1, x) + cc(S, x-c), where S1 is the set formed by removing c from S.
typedef int4 = (int, int, int, int) val theCoins = (1, 5, 10, 25): int4 fun coin_get (n: int): int = if n = 0 then theCoins.0 else if n = 1 then theCoins.1 else if n = 2 then theCoins.2 else if n = 3 then theCoins.3 else ~1 (* erroneous value *) // end of [coin_get] fun coin_change (sum: int) = let fun aux (sum: int, n: int): int = if sum > 0 then (if n >= 0 then aux (sum, n-1) + aux (sum-coin_get(n), n) else 0) else (if sum < 0 then 0 else 1) // end of [aux] in aux (sum, 3) end // end of [coin_change]
Note that the entire code in this section plus some additional code for testing is available on-line.