A problem statement from Arden Dertat’s “programming questions” series:

Given an integer array, output all pairs that sum up to a specific value k.

The first method need not be always the best method, but I try to get the result right without caring about the algorithm or efficiency.

This method uses two loops, and checks every pair (arr[i], arr[j]) with j > i, then stores the pair if arr[i] + arr[j] == k.

def pair_sum_bruteforce(arr, k):
    pairs = set()
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == k:
                pairs.add(tuple(sorted((arr[i], arr[j]))))
    return sorted(pairs)

This brute-force method is O(n^2) time.

An efficient method is to use a set for lookup. For each value x, compute the complement y = k - x (not absolute difference), and check whether y has already been seen.

def pair_sum_hashset(arr, k):
    seen = set()
    pairs = set()
    for x in arr:
        y = k - x
        if y in seen:
            pairs.add(tuple(sorted((x, y))))
        seen.add(x)
    return sorted(pairs)

This method is O(n) average time and O(n) extra space.

Also, this is the list-comprehension style approach, which is more concise but less efficient than the above method.

def pair_sum_listcomp(arr, k):
    pairs = {
        tuple(sorted((x, abs(k - x))))
        for x in arr
        if abs(k - x) in arr and x != abs(k - x)
    }
    return sorted(pairs)

This keeps the code short and uses set() to return unique pairs.