xlisponly/lsp/change.lsp

   1 ; Allow max of 9 of each coin
   2 (defun change (quan &optional (coins '(25 10 5  1)) &aux result)
   3        (cond ((zerop quan) (list nil))
   4              ((null coins) t)
   5              ((> (first coins) quan) (change quan (rest coins)))
   6              (t (dotimes (i (1+ (min 9 (/ quan (first coins)))))
   7                          (let ((res (change (- quan (* i (first coins)))
   8                                             (rest coins))))
   9                               (when (listp res)
  10                                   (if (zerop i)
  11                                       (setq result (append res result))
  12                                       (setq result (append (mapcar #'(lambda (x) (cons (list i (car coins)) x))
  13                                                                    res)
  14                                                            result))))))
  15                 (if (null result) t result))))