Most efficient method of getting possible sum from list in python
Question: Similar to knapsack problem. If I have

    
    
    list = [5,7,9,12,6]
    targetValue = 15
    

Since 6+9 = 15, what is the most efficient way of getting

    
    
    [6,9]
    

Does python have a built in method for such a problem?


Answer: Here's a quick solution. Note, however, that you could get duplicate solutions
if your list contains duplicate values.

    
    
    from itertools import *
    
    s = [5, 7, 9, 12, 6]
    m = 15
    
    c = chain(*[combinations(s, i) for i in range(len(s)+1)])
    r = [n for n in c if sum(n) == m]
    
    print r
    

Here's a more complicated version that handles duplicate values in the list:

    
    
    from itertools import *
    from collections import *
    
    s = [5, 7, 9, 12, 6]
    m = 15
    
    c = Counter(s)
    u = list(c)
    ul = len(u)
    t = [c[x] for x in u]
    p = product(*[xrange(i+1) for i in t])
    e = ([a for b in [[u[i]] * x[i] for i in range(ul)] for a in b] for x in p)
    r = [n for n in e if sum(n) == m]
    
    print r
    

