Python Program to Find Pairs with Given Sum in List

You can find pairs with a given sum in a list by using a set to track seen numbers and checking if the complement (target sum minus current number) exists, like this: seen = set(); pairs = []; for num in lst: if target - num in seen: pairs.append((num, target - num)); seen.add(num).

Examples

Inputlst = [1, 2, 3, 4, 5], target = 5

Output[(3, 2), (4, 1)]

Inputlst = [0, -1, 2, -3, 1], target = -2

Output[(-3, 1)]

Inputlst = [1, 1, 1, 1], target = 2

Output[(1, 1), (1, 1), (1, 1)]

How to Think About It

To find pairs that add up to a target sum, think about each number and what other number it needs to reach the target. Keep track of numbers you've seen so far. For each number, check if the needed partner is already seen. If yes, record the pair. This way, you only go through the list once.

Algorithm

1

Create an empty set to store numbers seen so far.

2

Create an empty list to store pairs found.

3

For each number in the list:

4

Check if (target sum - current number) is in the set of seen numbers.

5

If yes, add the pair to the list of pairs.

6

Add the current number to the set of seen numbers.

7

Return the list of pairs.

Code

python

def find_pairs(lst, target):
    seen = set()
    pairs = []
    for num in lst:
        complement = target - num
        if complement in seen:
            pairs.append((num, complement))
        seen.add(num)
    return pairs

# Example usage
lst = [1, 2, 3, 4, 5]
target = 5
print(find_pairs(lst, target))

Output

[(3, 2), (4, 1)]

Dry Run

Let's trace the example lst = [1, 2, 3, 4, 5] with target = 5 through the code

1

Start with empty seen set and pairs list

seen = {}, pairs = []

2

Process number 1

complement = 5 - 1 = 4; 4 not in seen; add 1 to seen; seen = {1}

3

Process number 2

complement = 5 - 2 = 3; 3 not in seen; add 2 to seen; seen = {1, 2}

4

Process number 3

complement = 5 - 3 = 2; 2 in seen; add (3, 2) to pairs; pairs = [(3, 2)]; add 3 to seen; seen = {1, 2, 3}

5

Process number 4

complement = 5 - 4 = 1; 1 in seen; add (4, 1) to pairs; pairs = [(3, 2), (4, 1)]; add 4 to seen; seen = {1, 2, 3, 4}

6

Process number 5

complement = 5 - 5 = 0; 0 not in seen; add 5 to seen; seen = {1, 2, 3, 4, 5}

Number	Complement	Complement in seen?	Pairs	Seen set
1	4	No	[]	{1}
2	3	No	[]	{1, 2}
3	2	Yes	[(3, 2)]	{1, 2, 3}
4	1	Yes	[(3, 2), (4, 1)]	{1, 2, 3, 4}
5	0	No	[(3, 2), (4, 1)]	{1, 2, 3, 4, 5}

Why This Works

Step 1: Track seen numbers

We use a set to remember numbers we have already checked, so we can quickly find if the needed partner number exists.

Step 2: Check for complement

For each number, we calculate the complement by subtracting it from the target sum and check if this complement is in the seen set.

Step 3: Store pairs

If the complement is found, we add the pair to the result list, ensuring we capture all pairs that sum to the target.

Alternative Approaches

Brute Force Nested Loops

python

def find_pairs_brute(lst, target):
    pairs = []
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            if lst[i] + lst[j] == target:
                pairs.append((lst[i], lst[j]))
    return pairs

print(find_pairs_brute([1, 2, 3, 4, 5], 5))

Simple but slower because it checks every pair; time complexity is higher.

Sorting and Two Pointers

python

def find_pairs_two_pointers(lst, target):
    lst.sort()
    left, right = 0, len(lst) - 1
    pairs = []
    while left < right:
        current_sum = lst[left] + lst[right]
        if current_sum == target:
            pairs.append((lst[left], lst[right]))
            left += 1
            right -= 1
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return pairs

print(find_pairs_two_pointers([1, 2, 3, 4, 5], 5))

Efficient for sorted lists; uses sorting and two pointers to find pairs.

Complexity: O(n) time, O(n) space

Time Complexity

The main approach loops through the list once, checking and adding elements to a set, which takes O(1) time per operation, resulting in O(n) total time.

Space Complexity

We use a set to store seen numbers, which can grow up to size n in the worst case, so space complexity is O(n).

Which Approach is Fastest?

The set-based approach is fastest for unsorted lists with O(n) time. The two-pointer method is also efficient but requires sorting first, which is O(n log n). The brute force method is slowest at O(n^2).

Approach	Time	Space	Best For
Set-based single pass	O(n)	O(n)	Unsorted lists, fast lookup
Sorting and two pointers	O(n log n)	O(1)	Sorted lists or when sorting is acceptable
Brute force nested loops	O(n^2)	O(1)	Very small lists or simple implementation