Making Change with Exceptions (Backtracking)

The problem with greed

The greedy change algorithm fails when the largest-coin-first strategy leads to a dead end (e.g., making 6 from [5, 2]). We need a way to undo a coin choice and try alternatives: this is backtracking.

Exception-driven backtracking

The idea is elegant: enclose each recursive call in an exception handler. If the recursive call fails (raises Change), the handler catches it and tries the next alternative.

exception Change

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

How it works

• If amt = 0: success, return [].
• If the till is empty or amt goes negative: dead end, raise Change.
• Otherwise: try using the largest coin. If the recursive call raises Change, catch it and try the next coin instead.

The exception handler always undoes the most recent choice. If all alternatives fail, Change propagates to the previous handler, and so on. If change is truly impossible, Change reaches the top level uncaught.

Trace: change [5; 2] 6

change [5; 2] 6
→ try 5::change [5; 2] 1
→ try 5::(try 5::change [5; 2] (-4)    ← amt < 0, raise Change
           with Change → change [2] 1)
→ try 5::(try 2::change [2] (-1)       ← amt < 0, raise Change
           with Change → change [] 1)   ← empty till, raise Change
→ change [2] 6                          ← handler caught it, try [2]
→ try 2::change [2] 4
→ try 2::(try 2::change [2] 2
→ try 2::(try 2::(try 2::change [2] 0  ← amt = 0, success: []
           with Change → change [] 2)
→ [2; 2; 2]                             ← success!

Observe how handlers nest as the recursion deepens, and drop away once a branch succeeds.

Comparison with list-of-all-solutions

Approach	Returns	Space	Use case
All solutions (list)	All possibilities	Exponential	When all solutions are needed
Backtracking (exceptions)	First solution found	O(recursion depth)	When one solution suffices

Backtracking is dramatically more space-efficient and faster when only one solution is needed, since it stops searching upon success and does not accumulate partial results.