# Project Euler Problem 31

Project Euler Problem 31 asks us to find the number of possible English coin combinations that add up to £2.

Creating a full enumeration of all possible coin combinations involving 200 coins and then filtering it would be prohibitively expensive, so instead I adopted a recursive definition that that only looks at valid combinations:

(def coins [200 100 50 20 10 5 2 1])

(defn coin-combos [sum goal maxcoin]
(let [valid (filter #(and (>= maxcoin %)
(>= (- goal sum) %)) coins)]
(if (empty? valid)
(if (= sum goal) 1 0)
(reduce + (map #(coin-combos (+ sum %) goal %) valid)))))

(defn euler-31 []
(coin-combos 0 200 200))

This works, and takes about 4.5 seconds to execute. However, bibi’s solution on clojure-euler blows that out of the water, taking less than 100ms to execute:

(def coins [200 100 50 20 10 5 2 1])

(defn change[c v]
(let [f (first c)]
(if (= f 1) 1
(reduce + (for [n (range 0 (inc (quot v f)))]
(change (rest c) (- v (* n f))))))))

(defn euler-31-bibi []
(change coins 200))

Nice work, bibi!