My solution to a problem seen on http://opengarden.com/careers.html in ruby.

census.rb

#!/usr/bin/ruby
#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.

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]
target    = 100000000

# sum up the total of the elements of array
def total(arr)
  arr.inject { |total, n| total + n }
end

def find_sol(arr, target)
  if target > 0
    arr.each do |el|
      if el == target
        return [el]
      elsif el < target
        sub_arr = arr[(arr.index(el)+1)..-1]
        ans = find_sol(sub_arr, target - el)

        if ans.length > 0
          return [el] + ans
        end
      end
    end
  end
  []
end

# sort populations descending
answer = find_sol(populations.sort { |x,y| y <=> x }, target)
puts answer.to_s
puts "Total: " + total(answer).to_s