I purchased something for $1.79.

There is no unique answer, even if you restrict the coins to quarters,
dimes, nickels, and pennies.  There are two solutions in that case, and
the number of solutions grows to 11 if you allow half dollars and
dollar coins.

        $1.00   $.50    $.25    $.10    $.05    $.01
        -----   ----    ----    ----    ----    ----
           0      0       5       5       0       4
           0      0       6       1       3       4
           0      1       3       4       2       4
           0      1       4       0       5       4
           0      2       0       7       1       4
           0      2       1       3       4       4
           0      3       0       2       0       9
           1      0       0       6       3       4
           1      0       1       2       6       4
           1      0       2       2       0       9
           1      1       0       1       2       9

Although the principle involved is simple, it is difficult to carry out
without a computer.  The idea is to write a function to compute the
coin counts, given the desired amount, the required number of coins,
and the denominations (represented in cents).

As a first step, the function finds that to make a total of 179 with 14
coins with denominations in the list (100 50 25 10 5 1), the number of
"100" coins (dollar coins) obviously must be either zero or one.  This
reduces the stated problem to two subproblems:

        1. Find all ways to produce 179 with 14 coins in (50 25 10 5 1),
           and
        2. Find all ways to produce 79 with 13 coins in (50 25 10 5 1),
           adding a dollar coin to each of the second group of
           solutions.

Each case is simpler than the original problem because the dollar coins
have been eliminated from consideration, and in case 2 there also is a
reduction in the total and in the number of coins to be used.  The
function may then call itself to solve each of these subcases.

The first case obviously requires that the number of 50-cent coins must
be either 0, 1, 2, or 3.  In like manner, the function reduces each of
those subcases to get a simpler problem of the same type, following
each branch of the solution tree until all the solutions are found.

A lisp function to carry out the computation is as follows:

(defun make-change (amount num-coins coin-list)
  "List ways of making amount with exactly num-coins values chosen
   from coin-list."
  (if (null coin-list) ; no coins left to use:  amount and num-coins must be 0
    (if (and (zerop amount) (zerop num-coins))
      '(())     ; there is exactly one solution and it is empty
      '())      ; there are no solutions
    ;; otherwise at least one denomination of coin is left to use
    ;; find possible number of times coin could be used
    ;; generate and solve all corresponding sub-problems
    (loop with first-coin = (first coin-list)
          for first-num from 0 to (min num-coins (floor amount first-coin))
          append (mapcar #'(lambda (x) (cons first-num x))
                         (make-change (- amount (* first-num first-coin))
                                      (- num-coins first-num)
                                      (rest coin-list))))))

A sample call to solve the given problem is:

        (make-change 179 14 '(100 50 25 10 5 1))

which produces the result

((0 0 5 5 0 4)(0 0 6 1 3 4)(0 1 3 4 2 4)(0 1 4 0 5 4)(0 2 0 7 1 4)(0 2 1 3 4 4)
 (0 3 0 2 0 9)(1 0 0 6 3 4)(1 0 1 2 6 4)(1 0 2 2 0 9)(1 1 0 1 2 9))

-- Dave Seaman <ags@seaman.cc.purdue.edu>