Change Maker in clojure

dynamic.clj

(ns katas.change-maker)

(defn num-pairs
  "Returns all combinations of [x y] and (<= x y) where (= cents (+ x y))"
  [cents]

  (for [x (reverse (range 1 (inc (quot cents 2)))) ;; use the range from midpoint to 1 so that we walk the 
                                                   ;; shortest side of the tree first
        :let [y (- cents x)]]
    [x y]))

;; Not tail recursive so can blow the stack
(defn change-maker
  ([cents] (change-maker cents '(25 10 5 1)))
  ([cents coins]
     (cond
      (zero? cents) []
      (some #{cents} coins) [cents]
      :else (let [pairs (num-pairs cents)
                  stacks (for [[x y] pairs]
                           (concat
                            (change-maker x coins)
                            (change-maker y coins)))
                  optimal-stack (apply min-key count stacks)]
              (sort-by - optimal-stack)))))

(alter-var-root #'change-maker memoize)

greedy-recursive.clj

(ns katas.change-maker)

;; tail recursive but naive — will miss some test cases
(defn change-maker
  ([cents] (change-maker cents '(25 10 5 1) []))
  ([cents coins] (change-maker cents coins []))
  ([cents coins change]
     (if (or (zero? cents) (empty? coins))
       change
       (let [coin (apply max (filter (partial >= cents) coins))]
         (recur (- cents coin) coins (conj change coin))))))

tests.clj

(ns katas.change-maker-test
  (:use clojure.test
        katas.change-maker))

(deftest change-maker-tests
  (are [cents coins] (= (change-maker cents) coins)
       0  []
       26 [25 1]
       24 [10 10 1 1 1 1]
       49 [25 10 10 1 1 1 1]
       1000 (repeat 40 25))    ;; this will blow the stack for a suboptimal recursively memoized implementation

  (are [cents coins] (= (apply change-maker cents) coins)
       '(26 [10 25 1 5]) [25 1]

       ;; the following two won't work with a greedy change maker:
       '(24 [10 7 1])    [10 7 7]
       '(14 [10 7 1])    [7 7]))