# Problem

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

# Solution

## Brute-force

We can compute all combinations of 2 elements in the list and then verify if they adds up to k.

``````def solve(list_of_numbers, k):
for index_1, element_1 in enumerate(list_of_numbers):
for index_2, element_2 in enumerate(list_of_numbers):
if index_1 != index_2:
if element_1 + element_2 == k:
return True
return False``````

This run in O(N²) due to the nested loop.

## Using a set

As we iterate over the list we can store in a set the elements we’ve seen so far.

We can then check if weather or not we have seen the complement (difference with k) before.

``````def solve(list_of_numbers, k):
seen = set()
for element in list_of_numbers:
complement = k - element
if complement in seen:
return True
else:
seen.add(element)
return False``````

This run in O(N) since we iterate over the list once and lookup in a set is O(1).