Technology

# Trivial subset sum problem

I was asked in a telephone interview how to find out if there are two numbers in
a list that sum to a certain value. I did an O(N^2) algorithm, then refined it to an O(n lg n) algorithm. Unfortunately, there’s an O(n) algorithm which I didn’t think of on the phone but came up with after the fact:

```def somePair(values, Z):
"""
Given a list of numbers and value Z, are there any pair of numbers such that X+Y = Z?
This does this in O(N) time looking at each value, val, and checking if Z-val is
"""
lookup = set()         # Store the values
for val in values:
diff = Z - val
if diff in lookup:
return True
else:
return False
if __name__ == '__main__':
assert somePair([], 4) == False
assert somePair([4], 4) == False
assert somePair([1,2,3,4], 1) == False
assert somePair([1,2,3,4], 2) == False
assert somePair([-8, 12], 4)
assert somePair([1,2,3,4], 3)
assert somePair([1,2,3,4, 4], 3)
assert somePair([1,2,3,4], 4)
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.