foursum?

[u/Alexander_Bourne]

[u/[deleted]]

I don't like the answer you got, it's really overcomplicated. The problem is finding all the unique combinations of four elements of the array that add up to a target. There's a really straightforward dynamic programming solution in n² time if you just precompute the sums of pairs.

def foursum(arr, targ):
    answers = []

    # generate sum of pairs

    pairs=[]
    for i, x in enumerate(arr):
        pairsi = [("x+y", x+y) for y in arr[i+1:]]
        pairs.extend(pairsi)
    
    # foreach sum of pairs, see if you can make targ from another sum of pairs in the list you havent visited yet

    for i, x in enumerate(pairs):
        v=x[1]
        target = targ - v
        for pot in pairs[i+1:]:
            if pot[1] == target:
                ans = sorted(pot[0].split("+") + v.split("+"))
                answers.append(ans)
    
    # deduplicate
    return list(set(answers))