CODEWITHSUNDEEP
pythonlistsumcombinations
Krypton
Krypton

Reputation: 233

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

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.

Upvotes: 7

Views: 11381

Answers (8)

Bhaskar Pathak
Bhaskar Pathak

Reputation: 1

a = [5,2,3,9,1]
b = []
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if (a[i] + a[j] == 10):
            b.append((a[i],a[j]))
print(b)

Upvotes: 0

Zorro
Zorro

Reputation: 57

#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)

Upvotes: 0

Giao Nguyen
Giao Nguyen

Reputation: 1

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

Upvotes: 0

lollercoaster
lollercoaster

Reputation: 16493

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.

Upvotes: 4

Peter DeGlopper
Peter DeGlopper

Reputation: 37319

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.

Upvotes: 2

roippi
roippi

Reputation: 25954

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.

Upvotes: 3

Darrick Herwehe
Darrick Herwehe

Reputation: 3722

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

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

Upvotes: 3

Nafiul Islam
Nafiul Islam

Reputation: 82440

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)]

Upvotes: 10

Related Questions