Finding Combinations to the provided Sum value

Question

I have series of numbers like this

myvar = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]

Now I want to calculate all such possible combinations (of length 1 to 20) whose sum is equal to a given number m.

I tried to solve with following code as :

def sum_count(m):    ## Where m is the sum required

    from itertools import combinations

    myseq = []
    for i in range(1,len(myvar)):
        mycomb = list(combinations(mass,i));  # Getting combinations of length i
        mycomb = [list(j) for j in mycomb];
        for j in range(len(mycomb)-1,-1,-1):
            if sum(mycomb[j]) == m:
                myseq.append(mycomb[j])

    return(myseq)

When I put m = 270 (for example) it gives me :

[[114, 156], [57, 99, 114]]

But is quite evident from the myvar that there are still other combinations which have a sum equal to 270. Where am I failing to comprehend.

Its is very inefficient. You should use Subset sum - DP Solution. — thefourtheye, Nov 25 '13 at 12:50
well I am not very much aware of Dynamic Programming... A detailed explanation or modified version of above will help me out — Ashutosh, Nov 25 '13 at 12:54
And the complete `sum_count` function's body can be simplified to `return [j for i in range(1, len(mass) + 1) for j in combinations(mass, i) if sum(j) == m]` — thefourtheye, Nov 25 '13 at 12:57
by the way who downvotes such questions?? Do these people think everybody to be programmer experts ??? — Ashutosh, Nov 25 '13 at 13:19
@Ashutosh Welcome to StackOverflow; Please do not be upset at receiving downvotes - it can be for many reasons, usually because as the downvote button suggests people might think you have no put much research or effort into your question, or that it is unclear or not useful to the general public. Indeed - your question has some formatting issues, and deals with a problem that is mostly only important and relevant to you - not the public as a whole. And based on the comments, some people find it unclear. So - instead of being angry at others, realize what you can improve. — Inbar Rose, Nov 25 '13 at 13:22
people downvote questions if they feel the asker hasn't abided by or read the rules for posting a question. It wasn't me btw :) — Totem, Nov 25 '13 at 13:23

score 9 · Accepted Answer · edited Jan 18 '21 at 12:34

TL;DR:

Discuss different methods, best method is listed here for ease of access and was originally written by thefourtheye:

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u + x, l + [lst[u]], r, t)
        return r
    return _a(0, [], [], target)

note: the above method is modified with improvements from the original version below

Original Post:

Well - A quick and simple application of your data with some logic concludes that you have the correct answer:

# data
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]
target = 270

Using itertools.combinations:

>>> from itertools import combinations
>>> [comb for i in range(1, 20) for comb in combinations(vals, i) if sum(comb) == target]
[(114, 156), (57, 99, 114)]

However, maybe you wanted to use combinations_with_replacement which lets values be used multiple times from the initial list as opposed to only once.

Using itertools.combinations_with_replacement:

>>> from itertools import combinations_with_replacement
>>> [comb for i in range(1, 20) for comb in combinations_with_replacement(vals, i) if sum(comb) == target]
>>>  # result takes too long ...

You can make it into a robust function:

def subsets_with_sum(lst, target, subset_lengths=range(1, 20), method='combinations'):   
    import itertools
    return [comb for i in subset_lengths for comb in
            getattr(itertools, method)(lst, i) if sum(comb) == target]

>>> subsets_with_sum(vals , 270)
[(114, 156), (57, 99, 114)]

Another method, provided by thefourtheye , it is much faster, and requires no imports:

def a(lst, target, with_replacement=False):
    def _a(idx, l, r, t, w):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u if w else (u + 1), l + [lst[u]], r, t, w)
        return r
    return _a(0, [], [], target, with_replacement)


>>> s = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]
>>> a(s, 270)
[[57, 99, 114], [114, 156]]
>>> a(s, 270, True)
[[57, 57, 57, 99], [57, 57, 156], [57, 71, 71, 71], [57, 99, 114], [71, 71, 128], [114, 156]]

Timing:

def a(lst, target, with_replacement=False):
    def _a(idx, l, r, t, w):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u if w else (u + 1), l + [lst[u]], r, t, w)
        return r
    return _a(0, [], [], target, with_replacement)

def b(lst, target, subset_lengths=range(1, 21), method='combinations'):   
    import itertools
    return [comb for i in subset_lengths for comb in
            getattr(itertools, method)(lst, i) if sum(comb) == target]
    
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]

from timeit import timeit
print 'no replacement'
print timeit("a(vals, 270)", "from __main__ import vals, a", number=10)
print timeit("b(vals, 270)", "from __main__ import vals, b", number=10)
print 'with replacement'
print timeit("a(vals, 270, True)", "from __main__ import vals, a", number=10)
print timeit("b(vals, 270, method='combinations_with_replacement')", "from __main__ import vals, b", number=10)

Timing Output:

no replacement
0.0273933852733
0.683039054001
with replacement
0.0177899423427
... waited a long time ... no results ...

conclusion:

The new method (a) is at least 20 times faster.

The `with_replacement` keyword argument isn't actually _used_ for anything in the `a()` or `_a()` functions (except being passed from the former to the latter so it can ignore it, too). — martineau, Oct 20 '17 at 18:38
Thank you, @InbarRose! The function `subsets_with_sum()` helped me a lot. I know what recursion is, but, since I rarely or never use it, the function is feeling very abstract to me right now. Could you help me to understand how the function works? — Guilherme, Oct 16 '19 at 13:17
@Guilherme there is no recursion here. This post is almost 6 years old. You might want to ask a new question if you need help with something. — Inbar Rose, Oct 16 '19 at 13:29
https://stackoverflow.com/questions/58415182/function-that-find-combination-of-values-that-sums-to-a-given-number posted here, thanks. — Guilherme, Oct 16 '19 at 14:00

score 6 · Answer 2 · answered Jul 28 '14 at 01:11

If you simply want a count of the number of combinations then use this:

aminoacid_masses = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]


def peptides(n, d):
    for m in aminoacid_masses:
        if n-m in d:
            d[n] = d.get(n,0)+d[n-m]
    return d


def pep_counter(M):
    dicc = {0:1}
    mn = min(aminoacid_masses)
    for i in range(M-mn+1):
        j = i+mn
        peptides(j,dicc)
    return dicc


# This line calls the routine and indexes the returned dict.  Both with the desired mass (the mass we want peptides to sum up to)
print(pep_counter(1024)[1024])

Finding Combinations to the provided Sum value

2 Answers2

Linked

Related