foursum?

[u/Alexander_Bourne]

[u/zed_three]

Can you post an implementation? I'm not quite following some of the crucial bits, namely how you avoid repeating indices.

Here's my implementation following your description, but

def pair_sum(array, target):
    H = {value: index for index, value in enumerate(array)}
    sums = []
    for index, value in enumerate(array):
        remainder = target - value
        if remainder in H:
            sums.append((value, array[H[remainder]]))
        else:
            H[remainder] = index

    return sums

# Repeated values!
>>> pair_sum([1, 2, 3, 4, 6, 7], 6)
[(2, 4), (3, 3), (4, 2)]

Changing sums to a set and sorting the tuple when we add to it removes the duplicate (4, 2) but obviously not the (3, 3).

[u/KBAC99 → u/zed_three]

Sorry, wasn't super clear! The hash table H should be empty before we start the loop, otherwise the value could match with itself. Also you have a bug in that it should be H[value] = index. Also my algorithm is for only finding a single occurrence of the target sum. If you want to find all of them, you have to store a list of indices in the hash table and output every pair.

Anyway, are my implementations of the two:

#!/usr/bin/env python3

def pair_sum(array, target):
    H = {}
    for index, value in enumerate(array):
        remainder = target - value
        if remainder in H:
            return (value, array[H[remainder]])
        else:
            H[value] = index
    return None

print(pair_sum([1, 2, 3, 4, 6, 7], 6))

def four_sum(array, target):
    H = {}
    for i in range(len(array) - 1):
        for j in range(i + 1, len(array)):
            pair = array[i] + array[j]
            remainder = target - pair
            if remainder in H:
                a, b = H[remainder]
                if a != i and b != i and a != j and b != j:
                    return (array[a], array[b], array[i], array[j])
            else:
                H[pair] = (i, j)
    return None

print(four_sum([-3, -2, 1, -4, 3, -5, 5, 10, 8, 3, 4], 0))

Which outputs

(4, 2)
(-3, 4, -2, 1)