Exercism: "Allergies in Clojure"

I solved the Allergies problem in Clojure.

This is my first iteration of the solution:

	(ns allergies)
	(declare allergies-by-score several-allergies, search-subset, searc-helper)
	(defn list [score]
	(if-let [one-match (get allergies-by-score score)]
	[one-match]
	(several-allergies score)))
	(defn allergic_to? [score stuff]
	(some #{stuff} (list score)))
	(def ^:private allergies-by-score
	{ 1 "eggs"
	2 "peanuts"
	4 "shellfish"
	8 "strawberries"
	16 "tomatoes"
	32 "chocolate"
	64 "pollen"
	128 "cats"})
	(defn- several-allergies [score]
	(let [possible-allergies-ids (filter #(< % score) (keys allergies-by-score))]
	(if (empty? possible-allergies-ids)
	[]
	(map #(get allergies-by-score %)
	(search-subset
	score
	possible-allergies-ids)))))
	(defn- searc-helper [score num-set nums]
	(if (> score (reduce + (keys allergies-by-score)))
	(let [max-num (apply max nums)]
	(searc-helper (- score max-num)
	(conj num-set max-num)
	nums))
	(if (empty? nums)
	false
	(let [current-num (first nums)
	sum (+ current-num (reduce + num-set))
	num-set-with-current-num (conj num-set current-num)]
	(cond (= score sum) num-set-with-current-num
	(> score sum) (if-let [res (searc-helper score num-set-with-current-num (rest nums))]
	res
	(searc-helper score num-set (rest nums)))
	(< score sum) (searc-helper score num-set (rest nums)))))))
	(defn- search-subset [score nums]
	(searc-helper score #{} nums))

view raw allergies1.clj hosted with ❤ by GitHub

And this is the second one which is tail-recursive:

	(ns allergies)
	(def ^:private allergies-by-score
	(sorted-map 1 "eggs"
	2 "peanuts"
	4 "shellfish"
	8 "strawberries"
	16 "tomatoes"
	32 "chocolate"
	64 "pollen"
	128 "cats"))
	(defn- sum-subset [sum nums]
	(loop [s sum
	i (dec (count nums))
	acc-set #{}]
	(if (or (zero? s) (neg? i))
	acc-set
	(let [num (nth nums i)]
	(if (>= s num)
	(recur (- s num) i (conj acc-set num))
	(recur s (dec i) acc-set))))))
	(defn list [score]
	(let [possible-allergies-ids (filter #(<= % score)
	(keys allergies-by-score))]
	(vec (map #(get allergies-by-score %)
	(sum-subset score possible-allergies-ids)))))
	(defn allergic_to? [score stuff]
	(some #{stuff} (list score)))

view raw allergies2.clj hosted with ❤ by GitHub

This problem was very interesting. To solve it you need to find a solution for a problem called subset sum. Both iterations use backtracking to find the subset of numbers that sum to the allergies score.

I had used this backtracking algorithm once before to solve the N-Queens problem in Racket for the Introduction to Systematic Program Design 1 Coursera course.

You can nitpick my solution here or see all the exercises I've done so far in this repository.