# Find smallest subset of integers having a given sum

Write a function that meets the specifications below:

def find_combination(choices, total):

"""
choices: a non-empty list of ints
total: a positive int

Returns result, a array of length len(choices) such that
* each element of result is 0 or 1
* sum(result*choices) == total
* sum(result) is as small as possible
In case of ties, returns any result that works.
If there is no result that gives the exact total,
pick the one that gives sum(result*choices) closest
to total without going over.
"""


My solution uses a brute force approach, but it is very slow. How can I implement a faster solution?

import itertools
import numpy as np

def find_combination(choices, total):
bins = np.array(list(itertools.product([0, 1], repeat=len(choices))))
combinations = [b for b in bins if sum(choices * b) == total]
return (min(combinations, key=sum) if combinations else
max([b for b in bins if sum(choices * b) < total], key=sum))

• Some examples here: If choices = [1,2,2,3] and total = 4 you should return either [0 1 1 0] or [1 0 0 1] If choices = [1,1,3,5,3] and total = 5 you should return [0 0 0 1 0] If choices = [1,1,1,9] and total = 4 you should return [1 1 1 0] – Tao Xu Jan 19 '17 at 2:56
• Looks like a Subset Sum problem (see en.wikipedia.org/wiki/Subset_sum_problem). Try DP. – vnp Jan 19 '17 at 6:36
• The docstring and parameters names don't match. This is misleading. – Mathias Ettinger Jan 19 '17 at 7:21
• Sorry, I corrected it. – Tao Xu Jan 21 '17 at 1:45