attempt.clj

(ns clojure-problems.core
  (:use clojure.set))

(def populations [18897109 12828837 9461105 6371773 5965343 5946800 5582170
                  5564635 5268860 4552402 4335391 4296250 4224851 4192887
                  3439809 3279833 3095313 2812896 2783243 2710489 2543482
                  2356285 2226009 2149127 2142508 2134411])

(defn summing-to [coll n]
  (cond (zero? n) '(())
        (empty? coll) '()
        :else (let [x (first coll)]
                (if (> x n)
                  '()
                  (lazy-cat (for [s (summing-to (rest coll) (- n x))]
                              (cons x s))
                            (summing-to (rest coll) n))))))

(defn solve-census []
  (first (summing-to (sort-by - populations) 100000000)))

(time (solve-census))

problem definition

The 2010 Census puts populations of 26 largest US metro areas at 18897109, 12828837, 9461105, 6371773, 5965343, 5946800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279833, 3095313, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, and 2134411.

Can you find a subset of these areas where a total of exactly 100,000,000 people live, assuming the census estimates are exactly right? Provide the answer and code or reasoning used.