Problem 12: Find Pairs with Target Sum

Source: Dev.to

Problem Description

Write a function that finds all unique pairs of numbers in a list that add up to a given target sum.
The function should return a list of tuples, each tuple containing the pair in sorted order. Each pair must appear only once.

Example

find_pairs([1, 5, 7, -1, 5], 6)   # → [(1, 5), (-1, 7)]
find_pairs([2, 3, 4, 5], 9)      # → [(4, 5)]

Solution

Python Implementation

def find_pairs(lst, target):
    """
    Finds all unique pairs in the list that sum up to the target.
    Returns a list of tuples sorted within each pair.
    """
    seen = set()
    pairs_found = set()
    for num in lst:
        complement = target - num
        if complement in seen:
            pairs_found.add((min(num, complement), max(num, complement)))
        seen.add(num)
    return list(pairs_found)

# Test cases
print(find_pairs([1, 5, 7, -1, 5], 6))   # Output: [(1, 5), (-1, 7)]
print(find_pairs([2, 3, 4, 5], 9))      # Output: [(4, 5)]

Explanation

1. Tracking seen numbers – seen is a set that stores numbers we have already processed, allowing O(1) look‑ups.
2. Storing pairs – pairs_found is a set of tuples. Using a set guarantees that duplicate pairs are ignored.
3. Iterating through the list
   • For each num, compute its complement target - num.
   • If the complement is already in seen, a valid pair has been found.
   • Add the pair to pairs_found in sorted order using min and max to keep the tuple consistent.
4. Updating seen – After checking for a complement, add the current num to seen so it can serve as a complement for later elements.
5. Returning the result – Convert the set of pairs to a list before returning. The order of pairs in the list is not guaranteed, but each pair is unique and sorted.