Find the pairs of integers that sum to N

Question

Can it be made faster, and I am a newbie to complexity but I'm pretty sure the average case for this would be O(n). Am I wrong? Output for the first list should be: (1,9), (2,8), (5,5), (-11,21)

The program finds pairs of an array whose sum is equal to ten.

#find pairs of an array whose sum is equal to ten
#bonus do it im linear time

list1 = [1,1,2,1,9,9,5,5,2,3,745,8,1,-11,21]
list2 = [1,1,1,1,9,9,9,9,2,8,8,8,2,2,0,0,0]
list3 = ["dog", "cat", "penguin", 9, 1]
list4 = []

def find_pairs_sum_n(list1, n):
    set1 = set(list1)
    history = set()

    if not list1:
        print("list is empty")
        raise StopIteration
    if not all(isinstance(n, int) for n in list1):
        print("list must contain only integers")
        raise StopIteration

    for x in set1:
        history.add(x)
        if (n - x) in set1 and (n-x) not in history:
            yield (x, n - x)

        elif x == n/2 and list1.count(n/2) > 1:
            yield (int(n/2), int(n/2))


x = find_pairs_sum_n(list1, 10)
for i in x:
    print(i)

y = find_pairs_sum_n(list2, 10)
for i in y:
    print(i)

z = find_pairs_sum_n(list3, 10)
print(next(z))

w = find_pairs_sum_n(list4, 10)
print(next(w))

Answer 1

In no particular order, a few suggestions to make the code more Pythonic.

return from generator

You do not need to raise StopIteration in a generator, you can simply return. So this:

if not list1:
    print("list is empty")
    raise StopIteration
if ...

Could have been a bit simpler as:

if not list1:
    print("list is empty")
elif ...

Use an Exception for exceptions

It is generally bad practice to put prints into your computation routines. Instead consider using exceptions.

if not list1:
    raise ValueError("list is empty")

Then catch the exception like:

try:
    for j in find_pairs_sum_n(l, 10):
        print(j)
except ValueError as exc:
    print(exc)

You don't need history

Since the values you are evaluating are already unique by putting them into a set(), you don't need history. Instead, only do the evaluation for numbers which are < 1/2 of n.

Mid value check only once

For the mid-value check I suggest you do it only once (ie, not in the loop). Additionally if you use collections.Counter instead of the set() you don't need to do the list.count() because you already have the counts.

Consider using a generator expression

Now that we have simplified the loop somewhat, it can be pretty cleanly written as a generator expression:

yield from ((x, n-x) for x in values if x <= threshold and (n - x) in values)

Full code listing

from collections import Counter

def find_pairs_sum_n(values, n):
    values = Counter(values)
    non_ints = {x for x in values if not isinstance(x, int)}

    if non_ints:
        raise ValueError(
            "Found non-integers in values: {}".format(non_ints))

    threshold, n_odd = divmod(n, 2)
    if not n_odd:
        if values[threshold] > 1:
            yield threshold, threshold
        threshold -= 1

    yield from (
        (x, n-x) for x in values if x <= threshold and (n - x) in values)


list1 = [1, 1, 2, 1, 9, 9, 5, 5, 2, 3, 745, 8, 1, -11, 21]
list2 = [1, 1, 1, 1, 9, 9, 9, 9, 2, 8, 8, 8, 2, 2, 0, 0, 0, 4, 5, 6]
list3 = ["dog", "cat", "penguin", 9, 1]
list4 = []

for l in (list1, list2, list3, list4):
    try:
        for j in find_pairs_sum_n(l, 10):
            print(j)
    except ValueError as exc:
        print(exc)
    print('---')

Results:

(5, 5)
(1, 9)
(2, 8)
(-11, 21)
---
(1, 9)
(2, 8)
(4, 6)
---
Found non-integers in values: {'dog', 'penguin', 'cat'}
---
---