You are in a shop and have 10p. The following items are for sale: Muffin - 5p Milkshake - 3p Chocolate - 2p Gingerbread man - 1p You need to spend ALL your money. What combinations of items can you buy such that you spend all 10p?

example.clj

(def prices {:muffin 5 :milkshake 3 :chocolate 2 :gingerbread 1})

(clojure.pprint/pprint (shop 10 prices))
({:muffin 0, :chocolate 0, :milkshake 0, :gingerbread 10}
 {:muffin 0, :chocolate 0, :milkshake 1, :gingerbread 7}
 {:muffin 0, :chocolate 0, :milkshake 2, :gingerbread 4}
 {:muffin 0, :chocolate 0, :milkshake 3, :gingerbread 1}
 {:muffin 0, :chocolate 1, :milkshake 0, :gingerbread 8}
 {:muffin 0, :chocolate 1, :milkshake 1, :gingerbread 5}
 {:muffin 0, :chocolate 1, :milkshake 2, :gingerbread 2}
 {:muffin 0, :chocolate 2, :milkshake 0, :gingerbread 6}
 {:muffin 0, :chocolate 2, :milkshake 1, :gingerbread 3}
 {:muffin 0, :chocolate 2, :milkshake 2, :gingerbread 0}
 {:muffin 0, :chocolate 3, :milkshake 0, :gingerbread 4}
 {:muffin 0, :chocolate 3, :milkshake 1, :gingerbread 1}
 {:muffin 0, :chocolate 4, :milkshake 0, :gingerbread 2}
 {:muffin 0, :chocolate 5, :milkshake 0, :gingerbread 0}
 {:muffin 1, :chocolate 0, :milkshake 0, :gingerbread 5}
 {:muffin 1, :chocolate 0, :milkshake 1, :gingerbread 2}
 {:muffin 1, :chocolate 1, :milkshake 0, :gingerbread 3}
 {:muffin 1, :chocolate 1, :milkshake 1, :gingerbread 0}
 {:muffin 1, :chocolate 2, :milkshake 0, :gingerbread 1}
 {:muffin 2, :chocolate 0, :milkshake 0, :gingerbread 0})

shopping.clj

(defn basket-total [bskt] (reduce (fn [total [product qty]] (+ total (* (prices product) qty))) 0 bskt))

;; binary-like count with n 'bits' which can have values between from and to
;; e.g. (permutations 3 0 3) -> ([0 0] [0 1] [0 2] [1 0] [1 1] [1 2] [2 0] [2 1] [2 2])
(defn permutations [n from to]
  (let [symbols (into [] (take n (repeatedly gensym)))
         ranges (take n (repeatedly #(into [] (range from to))))
         bindings (into [] (interleave symbols ranges))]
    (eval `(for ~bindings ~symbols))))


(defn shop 
    "Given a certain amount of money, how many permutations of item can you buy?"
    [money prices]
    (filter #(= money (basket-total %))
      (map (fn [trial] (apply hash-map (interleave (keys prices) trial)))
        (permutations (count prices) 0 (inc (int (/ money (first (vals (sort-by second prices))))))))))