Editor

Python Program to Find Pairs with a Given Sum

Intermediate · Lists

This program finds every pair of numbers in a list that add up to a target, for example the pairs that make 11. It is a classic interview question, often called the two sum problem. The main program checks every pair with two loops, and the alternatives show faster methods.

Program

pairs_with_given_sum.py
numbers = [2, 7, 4, 5, 9, 1, 6]
target = 11 # or: target = int(input("Enter the target sum: "))
print("List:", numbers)
print(f"Pairs that add up to {target}:")
found = 0
for i in range(len(numbers)):
# j starts after i, so each pair is checked only once
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
print(f" {numbers[i]} + {numbers[j]} = {target}")
found += 1
if found == 0:
print(" No pairs found")
else:
print("Pairs found:", found)
Output
List: [2, 7, 4, 5, 9, 1, 6]
Pairs that add up to 11:
  2 + 9 = 11
  7 + 4 = 11
  5 + 6 = 11
Pairs found: 3

How it works

  1. The outer loop picks the first number of a pair, and the inner loop picks the second.
  2. The inner loop starts at i + 1, so a number is never paired with itself and the same pair is never printed twice, as 2 + 9 and 9 + 2.
  3. Every pair whose sum equals target is printed and counted.
  4. Checking every pair takes about n x n / 2 steps, which is fine for short lists but slow for long ones.

Other ways to write it

One pass with a set

One pass with a set
numbers = [2, 7, 4, 5, 9, 1, 6]
target = 11
seen = set()
for num in numbers:
partner = target - num # the number that would complete the pair
if partner in seen:
print(f"{partner} + {num} = {target}")
seen.add(num)
Output
7 + 4 = 11
2 + 9 = 11
5 + 6 = 11

For each number, the program asks whether its partner has already been seen. A set answers that quickly, so the list is read only once.

Two pointers on a sorted list

Two pointers on a sorted list
numbers = sorted([2, 7, 4, 5, 9, 1, 6])
target = 11
print("Sorted list:", numbers)
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
print(f"{numbers[left]} + {numbers[right]} = {target}")
left += 1
right -= 1
elif total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
Output
Sorted list: [1, 2, 4, 5, 6, 7, 9]
2 + 9 = 11
4 + 7 = 11
5 + 6 = 11

After sorting, one pointer starts at each end. A sum that is too small moves the left pointer up, and a sum that is too big moves the right pointer down.

Try it yourself

Set target to 20 to see the "No pairs found" message.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises