finding a sum of X numbers within a list (Python)

Question

i'm trying to find a combination for a sum inside a list of integers.

the amount of numbers that contain the sum is limited by a variable, so for example in the list -

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

so that the program would print out [9,1].

I'm new to python, is there an easy way of doing it?

thank you.

Solution 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 iterable object (an object you can loop 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)]

Solution 2

All so far have been O(N^2) or worse, so here's an 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, here's a more general look at the solution. We have:

• numbers (list of numbers)
• sum (desired sum)
• n (number of elements we desire to sum to sum)

The easiest is the following:

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 be able to get asymptotic O(|numbers|^(n-1)) by being more clever and caching sums of n - 1 size.

Solution 3

The 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 pairs that sum to 10. This is superexponential in run time, so if your inputs are large you will want a more sophisticated algorithm.

Solution 4

ls = [5, 2, 3, 9, 1]
sum = 10

while ls:
    num = ls.pop()
    diff = sum - num
    if diff in ls:
        print([num, diff])

Solution 5

Just for code golf purposes, here's the collections.Counter approach:

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'd need to use a defaultdict instead. It's not much more complex.

I think this is harder to read than the itertools.combinations version @roippi posted, but it should be significantly faster if the list of integers is large. I usually value human time reading the code over machine time executing it, but which consideration wins will depend on your exact situation.

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

View more solutions

Comments

[Peter DeGlopper]

I think you could theoretically save some processing time by exploiting the fact that once you know your first number, you also know the second and can check for its presence in the list (probably using a collections.Counter object created from the list to speed up the repeated membership tests, decrementing as you output each pair) but it gets more confusing than this. Clarity probably wins out for the vast majority of cases.

[roippi]

@PeterDeGlopper yeah, I added a note about time complexity. I imagine for the majority of uses this is sufficient.

[Peter DeGlopper]

I disagree that my Counter solution is O(N^2). One traversal to create the Counter, one traversal to search for pairs, and N dictionary lookups. This version is close to mine, but can't handle cases like [4, 6, 6] correctly. I think there is some benefit in the idea, though - just use a Counter instead of a set, and you might get performance benefits from iterating only once. Depending on how much faster the Counter constructor can handle a list rather than having multiple edits made - C implementation might beat the algorithmic improvement.

[lollercoaster]

True, but given the question asks for "a combination" as opposed to "all combinations", this answers the question in 2N as opposed to your 3N. Which is not really that different - so yes we're both linear!

[Peter DeGlopper]

Yeah, O(N) rather than O(N^2) is all that's usually important. And it turns out that it could be important what the behavior on possible duplicates is - itertools would find (4,6) twice in that mini-example. The OP did not specify, so your version could be closer to the intent.

[Krypton]

while i like the approach of not using itertools better, what i originally inteded was to have a variable that determines how many numbers in the list it would take to make the sum. so the variable could be 3 as well as 2, and still get the result... that said, is there an elegant way of doing it without using itertools? (please bear with me because as I said i'm quite new to python :) )

[lalithkumar]

Is this best approach in order to get the time complexity?