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 (range 1 cents)
        :let [y (- cents x)]
        :when (<= x y)]
    [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)]
              (reverse (sort 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)
       26 [25 1]
       24 [10 10 1 1 1 1]
       49 [25 10 10 1 1 1 1]
       0  [])

  (are [cents in-coins out-coins] (= (change-maker cents in-coins) out-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]))

I bet changing line 7 to (reverse (range 1 cents)) would cause it to not blow the stack on any reasonable input.

Also the second set of tests can be a little cleaner since are supports more than two bindings:

(are [cents in-coins out-coins] (= (change-maker cents in-coins) out-coins)
  26 [10 25 1 5] [25 1]
  ...)

Oh duh... I didn't even think about having more than two bindings. That's pretty fricking obvious :P. Damn it >.<