How to check if N can be expressed as sum of two other numbers in specific list

Question

I have a list:

l = [1,3,4,6,7,8,9,11,13,...]

and a number n.

How do I efficiently check if the number n can be expressed as the sum of two numbers (repeats are allowed) within the list l.

If the number is in the list, it does not count unless it can be expressed as two numbers (e.g for l = [2,3,4] 3 would not count, but 4 would.

This, embarrassingly, is what I've tried:

def is_sum_of_2num_inlist(n, num_list): 

num_list = filter(lambda x: x < n, num_list)

for num1 in num_list:
    for num2 in num_list:
        if num1+num2 == n:
            return True

return False

Thanks

Answer 1

def summable(n, l):
    for v in l:
        l_no_v = l[:]
        l_no_v.remove(v)
        if n - v in l_no_v:
            return True
    return False

EDIT: Explanation...

The itertools.cominations is a nice way to get all possible answers, but it's ~4x slower than this version since this is a single loop that bails out once it gets to a possible solution.

This loops over the values in l, makes a copy of l removing v so that we don't add v to itself (i.e. no false positive if n = 4; l = [2, 1]). Then subtract v from n and if that value is in l then there are two numbers that sum up to n. If you want to return those numbers instead of returning True just return n, n - v.