Find all combinations of a list of numbers with a given sum
Solution 1
You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn't sum to 10:
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
target = 10
result = [seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]
print(result)
Result:
[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]
Unfortunately this is something like O(2^N) complexity, so it isn't suitable for input lists larger than, say, 20 elements.
Solution 2
The solution @kgoodrick offered is great but I think it is more useful as a generator:
def subset_sum(numbers, target, partial=[], partial_sum=0):
if partial_sum == target:
yield partial
if partial_sum >= target:
return
for i, n in enumerate(numbers):
remaining = numbers[i + 1:]
yield from subset_sum(remaining, target, partial + [n], partial_sum + n)
list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10))
yields [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]]
.
Solution 3
This question has been asked before, see @msalvadores answer here. I updated the python code given to run in python 3:
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print("sum(%s)=%s" % (partial, target))
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i + 1:]
subset_sum(remaining, target, partial + [n])
if __name__ == "__main__":
subset_sum([3, 3, 9, 8, 4, 5, 7, 10], 15)
# Outputs:
# sum([3, 8, 4])=15
# sum([3, 5, 7])=15
# sum([8, 7])=15
# sum([5, 10])=15
Solution 4
@qasimalbaqali
This may not be exactly what the post is looking for, but if you wanted to:
Find all combinations of a range of numbers [lst], where each lst contains N number of elements, and that sum up to K: use this:
# Python3 program to find all pairs in a list of integers with given sum
from itertools import combinations
def findPairs(lst, K, N):
return [pair for pair in combinations(lst, N) if sum(pair) == K]
#monthly cost range; unique numbers
lst = list(range(10, 30))
#sum of annual revenue per machine/customer
K = 200
#number of months (12 - 9 = num months free)
N = 9
print('Possible monthly subscription costs that still equate to $200 per year:')
#print(findPairs(lst, K, N))
findPairs(lst,K,N)
Results:
Possible monthly subscription costs that still equate to $200 per year:
Out[27]:
[(10, 11, 20, 24, 25, 26, 27, 28, 29),
(10, 11, 21, 23, 25, 26, 27, 28, 29),
(10, 11, 22, 23, 24, 26, 27, 28, 29),
The idea/question behind this was "how much can we charge per month if we give x number of months free and still meet revenue targets".
Solution 5
This works...
from itertools import combinations
def SumTheList(thelist, target):
arr = []
p = []
if len(thelist) > 0:
for r in range(0,len(thelist)+1):
arr += list(combinations(thelist, r))
for item in arr:
if sum(item) == target:
p.append(item)
return p
Byte Commander
Ask Ubuntu moderator♦, IT student and DevOps engineer. I love Ubuntu, Python, good music and coffee, although not necessarily in that order. You can easily contact me in the Ask Ubuntu General Room most of the time, or on Discord as @ByteCommander#2800. I'd also love to invite you to my Ubuntu Hideout Discord Server btw. PS: My profile picture is derived from "Wolf Tribals" by user HaskDitex (DeviantArt.com), which is under creative Commons 3.0 License. Currently I'm using the character "Dregg Morriss" from the game "Medieval Cop" by Vasant Jahav ("Gemini Gamer"). It can be found here.
Updated on November 24, 2021Comments
-
Byte Commander over 2 years
I have a list of numbers, e.g.
numbers = [1, 2, 3, 7, 7, 9, 10]
As you can see, numbers may appear more than once in this list.
I need to get all combinations of these numbers that have a given sum, e.g.
10
.The items in the combinations may not be repeated, but each item in
numbers
has to be treated uniquely, that means e.g. the two7
in the list represent different items with the same value.The order is unimportant, so that
[1, 9]
and[9, 1]
are the same combination.There are no length restrictions for the combinations,
[10]
is as valid as[1, 2, 7]
.How can I create a list of all combinations meeting the criteria above?
In this example, it would be
[[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]