# Example: Coin Changes for Fun

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.

In the following implementation, we fix S to be the set consisting of 1, 5, 10 and 25.

```//
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): 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]
//
```

The auxiliary function aux defined in the body of the function coin_change corresponds to the cc function mentioned above. When applied to 1000, the function coin_change returns 142511.

Note that the entire code in this section plus some additional code for testing is available on-line.