;; достоинства монет
(def coins #{1 2 3 5})

(defn solve [f sum]
  (cond
    ;; допустим, не существует ни одного способа разменять
    ;; отрицательную или нулевую сумму
    (<= sum 0) 0

    :else (let [subsums (map (partial - sum) coins)] ;для каждого
                                                     ;достоинства
                                                     ;монет формируем
                                                     ;подзадачу
            (+
             ;; решаем каждую подзадачу по отдельности и суммируем
             ;; результат
             (reduce + 0 (map (partial f f) subsums))
             ;; если текущая сумма равна достинству одной из монет, то
             ;; мы нашли еще один способ размена
             (if (coins sum) 1 0)))))

(println "---------- naive ----------")
(println "result:" (time (solve solve 20)))
(println "---------- memoized ----------")
(println "result:" (time (solve (memoize solve) 20)))