Subset sum (knapsack-like) problem

Given a list of integers.

Find the subset of that list that add up to a target value.

Methods tried:

• Brute force using "powerset" recipe in itertools documentation http://docs.python.org/library/itertools.html#recipes
• Exact recursive solution with memoization from Stackoverflow http://stackoverflow.com/questions/3420937/algorithm-to-find-which-number-in-a-list-sum-up-to-a-certain-number
• Approximate branch and bound solution from "Python Algorithms" by Hetland http://search.safaribooksonline.com/book/programming/python/9781430232377/hard-problems-and-limited-sloppiness/when_the_going_gets_tough_comma_the_smar
• Aproximate solution from Wikipedia http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm