Find pairs in an integer array whose sum is equal to n (bonus: do it in linear time) I gave this one a shot, and the code works. Am I on the right track? How can the code be improved? Also, I am unaware of how to determine if this would be linear time or not. Could someone maybe break that determination down for me?

'''
Problem statement: Find pairs in an integer array whose sum is equal to n (bonus: do it in linear time)

@author: Anonymous3.1415
'''

def pair_sum_to_n(integer_list, n):
    pairs = []
    #checks for the occurence of halfs
    if not n % 2:
        if integer_list.count(n/2) &gt; 1:
            pairs.append((n/2, n/2))
        integer_set = set(integer_list) - {n/2}
    #finds pairs of integers where x + (n - x) = n
    for x in integer_set:
        if (n - x) in integer_set:
            if (n - x, x) not in pairs:
                pairs.append((x, n - x))
    return pairs

integer_list = list(map(int, raw_input().strip().split(" ")))
pairs = pair_sum_to_n(integer_list, 10)
print(pairs)
The map by default returns a list. You do not need another wrapper around it.

Your current implementation is of \$ O(n^2) \$ complexity. The statement:

(n - x, x) not in pairs


is of \$ O(n) \$ time, which lies inside a loop with \$ O(n) \$.

To do this in linear time, generate a dict/hash where you store simply the \$ n - x \$ values in first iteration. In the second (and independent) iteration, simply append the pair $$ \left( min(x,\ n - x),\ max(x,\ n - x) \right) $$ for each x in your list, if the \$ O(1) \$ lookup in the dict is true.