Question

I got an Three Sum programming problem (Python), and able to come up a quick solution. However, after some more testing i found there seems to be a subtle bug in a test case.
Please help if you can shed some light on it.

The problem is - given an array of integer numbers, try to find the pairs of three numbers that can sum up to '0'. Examples:
array = [1, 0, -1, 2, 3, -2]
answer = [[1, 0, -1], [2, 0, -2]] # those triples add up to '0'

However, if the array is [12, 3, 1, 2, -6, 5, 0, -1, -8, 6]
answer = [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5], [-1, 0, 1]] # missing this: [-6, 0, 6] ?!
code:
```
A.sort()
print(A)

result = []
r = len(A) -1

for x in range(len(A) - 2):
left = x + 1 # for each value of x, left starts one greater
# and increments from there.
while (left < r): # left < right
# sums == all three
sums = A[x] + A[left] + A[r]
if (sums < 0): left += 1
if (sums > 0): r -= 1
if not sums: # 0 is False ---> Not False == True
result.append([A[x],A[left],A[r]])

left += 1 # increment left -when find a combination

print(result)

Answer 1

Answer:

  r = len(A) -1 # needs to be inside the for x ... loop

Explanation:

After appending a result sum to your output list, your value of r remains at its last value. In the case of {-6, 0, 6}, you miss this because r is pointing to "5" after having just located the triple {-8, 3, 5}.

When "left" is reset for a new value of x, "r" needs to be reset, too.

_____

Comment on the algorithm

You have an interesting algorithm here. When written as a procedure in Mathematica, it executes your example problem in 280 us. A less procedural approach that generates all subsets of length 3, then sums those, then picks the ones that have a sum of zero executes in 120 us. Of course, keeping lists of all subsets and their sums uses a lot more memory than your program does.