Get combinations of elements that add up to a target sum-CodePudding

Is it possible to get a elements of a list whose sum is equal to the variable sum? I tried with iteration. Maybe it is possible to do it if I want to get 2 elements from the list, but I don't have an idea how to do it for more elements.

def function(sum, a):
    h = []
    c = [1,2,3,4,5,6,7,8]
    return f'{sum} contains of {a} elements : {h}'

For example, if sum = 15 and a = 2 h should be equal to [7,8]. If sum = 15 and a = 3 h should be equal to [8,3,4] or [6,5,4] etc. Maybe h should be a dictionary, it will look better if there is more than 1 possibility. Is there any function like sum which I can use? Or any tip for me.

CodePudding user response：

You could do it by using what is called a list comprehension. Note that I've renamed the argument you called sum to total because it's the name of a built-in function (and I wanted to make use of it).

from itertools import combinations

def function(total, a):
    h = []
    c = range(1, 9)
    h = [combo for combo in combinations(c, a) if sum(combo) == total]
    return f'{total} contains of {a} elements : {h}'

print(function(15, 2))
print(function(15, 3))

Output:

15 contains of 2 elements : [(7, 8)]
15 contains of 3 elements : [(1, 6, 8), (2, 5, 8), (2, 6, 7), (3, 4, 8), (3, 5, 7), (4, 5, 6)]

Note:

If you really, really, really, wanted to name your argument sum, you could code it like this which to allow use of the built-in function — I'm not recommending this, it's slower and confusing to other folks, I'm mentioning it primarily just for your information.

import builtins
from itertools import combinations

def function(sum, a):
    h = []
    c = range(1, 9)
    h = [combo for combo in combinations(c, a) if builtins.sum(combo) == sum]
    return f'{sum} contains of {a} elements : {h}'

print(function(15, 2))
print(function(15, 3))

CodePudding user response：

Use itertools.combinations and sum (which means you can't name one of your parameters that!):

from itertools import combinations

def function(total, a):
    c = range(1, 9)
    h = next(x for x in combinations(c, a) if sum(x) == total)
    return f'{total} contains of {a} elements : {h}'

print(function(15, 2))
print(function(15, 3))

15 contains of 2 elements : (7, 8)
15 contains of 3 elements : (1, 6, 8)

CodePudding user response：

You can get all the combination sizes using a recursive function. Assuming that you don't have negative numbers in the list, the recursive function can short circuit the search for items that would exceed the target sum (making it more efficient than brute forcing through the power set of combinations):

def getSum(total,A,result=[]):
    for i,n in enumerate(A):           # Try each item as the first
        if n==total: yield result [n]  # total reached, yield a combination
        if n>=total: continue          # short circuit search if beyond total
        yield from getSum(total-n,A[i 1:],result [n]) # recurse with rest

Output:

for items in getSum(15,[1,2,3,4,5,6,7,8]):
    print(items)
    
[1, 2, 3, 4, 5]
[1, 2, 4, 8]
[1, 2, 5, 7]
[1, 3, 4, 7]
[1, 3, 5, 6]
[1, 6, 8]
[2, 3, 4, 6]
[2, 5, 8]
[2, 6, 7]
[3, 4, 8]
[3, 5, 7]
[4, 5, 6]
[7, 8]

If the items in the list are guaranteed to be in ascending order, this can be further optimized by changing if n>=total: continue to if n>=total: break because once an item reaches the target (or beyond), all subsequent items are also too large)

If you only want a specific size, you can add one more parameter to the function and use it in the condition that yields result [n]

For example:

def getSum(total,A,size=2,result=[]):
    for i,n in enumerate(A):
        if n==total and size==1: yield result [n]
        if n>=total or  size==1: continue
        yield from getSum(total-n,A[i 1:],size-1,result [n])

for items in getSum(15,[1,2,3,4,5,6,7,8],3):
    print(items)

[1, 6, 8]
[2, 5, 8]
[2, 6, 7]
[3, 4, 8]
[3, 5, 7]
[4, 5, 6]