count-change

gistfile1.clj

(defn count-change [amount denominations]
  (cond
    ; when no more money we win
    (= amount 0) 1
    ; coins left and no money left? we lose
    (= (count denominations) 0) 0
    ; start with the largest and work down
    :else (let [sorted-denominations (-> denominations sort reverse)
                ; get the largest
                d (first sorted-denominations)]
            ; add it all together and make sure we have a flat vector
            (reduce + (flatten (map #(let [subtraction-amount (* % d)
                                           ; range gives us a sequence to subvec it we need a vector
                                           coins-left (subvec (vec sorted-denominations) 1)]
                                       ; recurse :) subtracting the amount from the total and with a subset of the coins
                                       (count-change (- amount subtraction-amount) coins-left))
                                    ; 0 - N even divisions of the amount from the denomination
                                    (range (+ (int (/ amount d)) 1))))))))