Finding the sum of X numbers in a list (Python)

Question

I am trying to find a combination for a sum inside a list of integers.

the number of numbers containing the sum is limited by a variable, for example, in the list -

[5,2,3,9,1], I would like to find the sum of 10, only 2 numbers.

so that the program prints out [9.1].

I'm new to python, is there an easy way to do this?

thanks.

Answer 1

from itertools import combinations l = [5,2,3,9,1] for var in combinations(l, 2): if var[0] + var[1] == 10: print var[0], var[1] 

Combinations create all possible combinations of tuples from an tuples object (an object that you can iterate over). Let me demonstrate:

 >>> [var for var in combinations([1,2,3,4,5], 2)] [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)] >>> [var for var in combinations([1,2,3,4,5], 3)] [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)] 

Answer 2

So far, everyone has been O (N ^ 2) or worse, so here is the O (N) solution:

 l = [7, 9, 6, 4, 2] s = set([l[0]]) sum = 10 for num in l[1:]: diff = sum - num if diff in s: print num, diff else: s.add(num) 

Since the OP asked the question, here is a more general view of the solution. We have:

• numbers (list of numbers)
• sum (desired amount)
• n (the number of elements that we want to sum to sum )

The easiest way:

 def find_sum_tuple(numbers, sum, n): return [tup for tup in itertools.combinations(numbers, n) if sum(tup) == sum] 

However, not the best in terms of asymptotic performance. As I showed above, you should get the asymptotics O (| numbers | ^ ( n -1)), being smarter and cache sums of size n - 1 .

Answer 3

Brute force approach using itertools.combinations :

 In [6]: [pair for pair in itertools.combinations(li,2) if sum(pair) == 10] Out[6]: [(9, 1)] 

This gives you all the pairs whose sum is 10. This is a superexponential value at runtime, so if your inputs are large, you will need a more complex algorithm.

Answer 4

 ls = [5, 2, 3, 9, 1] sum = 10 while ls: num = ls.pop() diff = sum - num if diff in ls: print([num, diff]) 

Answer 5

For golf golf purposes only, here collections.Counter :

 import collections integers_list = [5,2,3,9,1] integer_counts = collections.Counter(integers_list) for x in integers_list: y = 10 - x if (x != y and integer_counts[y]) or (x == y and integer_counts[y] > 1): print (x, y) # Or, if building a new list, append instead of print integer_counts.subtract((x, y)) 

collections.Counter was added in 2.7. For earlier versions you need to use defaultdict . This is not much more complicated.

I think this is harder to read than the published version of itertools.combinations @roippi, but it should be significantly faster if the list of integers is long. I usually estimate human time by reading the code for the time spent by the machine, but the gain from which will depend on your exact situation.

Unlike the itertools version, this will not return duplicate pairs unless both elements are duplicated. EG, consider the list [4, 3, 6, 6]. The itertools version will generate two different pairs (4, 6) and return both of them; This version considers 4 consumed as soon as it matches the first 6 and will only return one. If duplication is desired, set will work instead of Counter , although the special case for 5 becomes more complicated if you don't create the set iteratively, as shown in @ lollercoaster's answer.

Answer 6

 lst = [5,2,3,9,1] lstLen = len(lst) pair = 0 for i in range(lstLen): for j in range(lstLen): if(j <= i ): continue if((lst[i] + lst[j]) == 10): pair +=1 print "[%s, %s]" % (lst[i], lst[j]) print "number of pair = %s" % pair 

Answer 7

 #for unsorted array - complexity O(n) def twoSum(arr, target): hash = {} if len(arr) < 2: return None for i in range(len(arr)): if arr[i] in hash: return [hash[arr[i]], i] else: hash[target - arr[i]] = i return None twoSum([3,2,8,6],11)