All Ways of Making Change

Returning all solutions

Instead of returning a single solution (or failing), we can return all possible ways of making change. The result type becomes int list list (a list of solutions, each solution a list of coins).

Base version

let rec change till amt =
  match till, amt with
  | _       , 0   -> [ [] ]
  | []      , _   -> []
  | c::till , amt -> if amt < c then change till amt
                     else let rec allc = function
                             | [] -> []
                             | cs :: css -> (c::cs) :: allc css
                          in
                             allc (change (c::till) (amt - c)) @
                                   change till amt

Key differences from the greedy version:

• Success base case: [[]] (a list containing the empty solution), not just []. This represents “there is one way: use no coins”.
• Failure base case: [] (empty list of solutions), rather than raising an exception.
• Two sources of solutions: either use the current coin (change (c::till) (amt - c)) or skip it (change till amt). The locally declared allc function prepends the current coin c to each solution from the first source, and the results are concatenated with @.

Stepwise refinement: faster version

The base version uses many :: and @ operations. A refined version introduces accumulating parameters to eliminate them:

let rec change till amt chg chgs =
  match till, amt with
  | _       , 0   -> chg::chgs
  | []      , _   -> chgs
  | c::till , amt -> if amt < 0 then chgs
                     else change (c::till) (amt - c) (c::chg)
                                 (change till amt chg chgs)

Parameter	Role
chg	Accumulates the coins chosen so far (replaces allc)
chgs	Accumulates the list of complete solutions (replaces @)

This version runs several times faster than the base version. The technique of starting with a simple program and incrementally improving it is called stepwise refinement.

Exponential blow-up

Even the refined version cannot escape the fundamental problem: the number of solutions grows rapidly. Using UK coins (50, 20, 10, 5, 2, 1), there are 4,366 ways to make change for 99. No algorithm can list all solutions faster than the number of solutions, so the runtime remains exponential in the amount.