Find All Numbers In A Integer List That Add Up To A Number

I was asked this question on an interview. Given the following list: [1,2,5,7,3,10,13] Find the numbers that add up to 5. My solution was the following: #sort the list: l.sort()

Solution 1:

This will return all elements of the powerset of the input that sum up to 5:

>>> input = [1,2,5,7,3,10,13]
>>> import itertools
>>> def powerset(l):
...     return itertools.chain.from_iterable((itertools.combinations(l, i) for i in range(len(l)+1)))
...
>>> filter(lambda v: sum(v) == 5, powerset(input))
[(5,), (2, 3)]

Solution 2:

another solution using dictionaries

from collections import Counter

l = [1,2,2,5,7,3,10,0,-5]
counter = Counter(l)
keys = counter.keys()
result = []
key = keys.pop()

while True:
  if 5-key in counter:
    result.append((key, 5-key))
    counter[key]-=1
    if counter[key]<=0:
      del counter[key]
      if len(keys) == 0:
        break
      key = keys.pop()
    counter[5-key]-=1
    if counter[5-key]<=0:
      del counter[5-key]
  else:
    del counter[key]        
    if len(keys) == 0:
      break
    key = keys.pop()

print(result)

you get

[(-5, 10), (5, 0), (3, 2)]

---

with len(l)==1000 timeit for proposal solutions:

from timeit import Timer

t = Timer(jose)
print t.timeit(number=1)
#0.00108003616333
t = Timer(dan)
print t.timeit(number=1)
#hangout
t = Timer(morgan)
print t.timeit(number=1)
#0.000875949859619 <--- best time
t = Timer(steven)
print t.timeit(number=1)
#0.0118129253387
t = Timer(sam) #OP
print t.timeit(number=1)
#0.0160880088806

Solution 3:

This is how I would do it:

from itertools import permutations
from random import randint


base_list = [randint(-10, 10) for x in range(20)]

def five_sum(base_list, combinations):
    has_negatives = any([base for base in base_list if base < 0])
    if not has_negatives:
        filtered_list = [base for base in base_list if base <= 5]
    else:
        filtered_list = base_list
    perms = list(permutations(filtered_list, combinations))
    filtered_perms = [perm for perm in perms if sum(perm) == 5]
    print(filtered_perms)
    for perm in set(filtered_perms):
        yield perm

print(base_list)
print(list(five_sum(base_list, 2)))

In an ideal world where I had unlimited Memory, I would replace the combinations parameter with perms = [list(permutations(filtered_list, i)) for i in range(len(filtered_list) + 1)]