# 4-sum algorithm optimization

I'm trying to map this problem into a 4-sum problem, and I find the time complexity is always $O(n^3)$. Is there a way to optimize time complexity, with constant additional space complexity $O(1)$?

Problem

Given an array A of unique integers, find the index of values that satisfy A + B =C + D, where A,B,C & D are integers values in the array. Find all combinations of quadruples.

def four_sum (numbers, target, start, end, exclude_index_set):
i = start
j = end
result = []
while i < j:
if i in exclude_index_set:
i += 1
elif j in exclude_index_set:
j -= 1
elif numbers[i] + numbers[j] == target:
result.append((numbers[i], numbers[j]))
i += 1
j -= 1
elif numbers[i] + numbers[j] > target:
j -= 1
else:
i += 1
return result

if __name__ == "__main__":
numbers = [1,2,3,4]
result = []
for i,v in enumerate(numbers):
for j in range(i+1, len(numbers)):
r = four_sum(numbers, v+numbers[j], i+1, len(numbers)-1, set([i,j]))
if len(r) > 0:
r.append(([numbers[i],numbers[j]]))
result.append(r)
print result

• If your goal is to output all quadruples, then you cannot get solution faster than O(n^4), because you have to generate the answer somehow. – yeputons Feb 7 '17 at 7:37
• @yeputons Since the numbers are unique, there can only be at max $O(n^3)$ solutions. This is because, for any given A, B, C, there can be at most one D that solves the equation. If duplicates were allowed, then up to n-3 values of D could solve the equation. – JS1 Feb 7 '17 at 9:43
• @JS1 you're right, I missed the fact that numbers are unique. However, one still has to find all of them if they are to be printed. – yeputons Feb 7 '17 at 11:17
• The problem statement seems to allow all doubled pairs of indices: n[a]+n[b] == n[a]+n[b] and n[a]+n[b] == n[b]+n[a] for any a,b in the index range, so there's always at least $2N(N-1)$ quadruples in the solution, where $N$ – the input array's length. – CiaPan Feb 7 '17 at 13:47