Find Values In List Which Sum To A Given Value

I'm trying to code up something simple and pythonic to identify combinations of values from a list which sum to a defined value, within some tolerance. For example: if A=[0.4,2,3,1

Solution 1:

Take a look at itertools.combinations

deffirst_attempt(A=A):
        for i in xrange(1,len(A)+1):
                print [comb 
                                for comb inlist(itertools.combinations(A,i)) 
                                if4.5 < sum(map(float, comb)) < 5.5
                                ]
## -- End pasted text --

In [1861]: %timeit first_attempt
10000000 loops, best of 3: 29.4 ns per loop

Output -

In[1890]: first_attempt(A=A)
[][(2, 3), (2, 2.6)][(0.4, 2, 3), (0.4, 2, 2.6), (0.4, 3, 1.4)][][][]

Solution 2:

Here's a recursive approach:

# V is the target value, t is the tolerance# A is the list of values# B is the subset of A that is still below V-tdefcombination_in_range(V, t, A, B=[]):
    for i,a inenumerate(A):
        if a > V+t:    # B+[a] is too largecontinue# B+[a] can still be a possible list
        B.append(a)

        if a >= V-t:   # Found a set that worksprint B

        # recursively try with a reduced V# and a shortened list A
        combination_in_range(V-a, t, A[i+1:], B)

        B.pop()        # drop [a] from possible list

A=[0.4, 2, 3, 1.4, 2.6, 6.3]
combination_in_range(5, 0.5, A)