Introduction

Finding all pairs in an array that add up to a target value is a classic algorithm problem. The right solution depends on what "all pairs" means: unique value pairs, index pairs, or pairs that respect duplicate counts.

That distinction matters because the implementation changes once duplicates appear. A clean O(n) hash-based solution is usually best, but only after the output rules are clear.

A Hash-Based Solution for Unique Value Pairs

If you want each value pair only once, track numbers seen so far and collect normalized pairs:

1def unique_pairs_with_sum(values, target):
2    seen = set()
3    pairs = set()
4
5    for value in values:
6        complement = target - value
7        if complement in seen:
8            pairs.add(tuple(sorted((value, complement))))
9        seen.add(value)
10
11    return sorted(pairs)
12
13
14print(unique_pairs_with_sum([1, 5, 7, -1, 5], 6))
15# [(-1, 7), (1, 5)]

This runs in O(n) average time and avoids duplicate value pairs such as (1, 5) being reported twice just because the list contains two 5 values.

That makes it a good default when the problem is about mathematical pairs rather than every matching occurrence.

Handling Duplicate Occurrences

Sometimes the requirement is stricter: each element may only be used as many times as it appears, so duplicates should generate repeated pairs when justified by the data.

For example, in [1, 5, 7, -1, 5] with target 6, there are two valid (1, 5) pairings because there are two distinct 5 entries.

One way to handle that is with a frequency map:

1from collections import Counter
2
3def counted_pairs_with_sum(values, target):
4    counts = Counter(values)
5    pairs = []
6
7    for value in list(counts.keys()):
8        complement = target - value
9        if value not in counts or complement not in counts:
10            continue
11
12        if value == complement:
13            pair_count = counts[value] // 2
14            pairs.extend([(value, complement)] * pair_count)
15            del counts[value]
16        elif value < complement:
17            pair_count = min(counts[value], counts[complement])
18            pairs.extend([(value, complement)] * pair_count)
19            del counts[value]
20            del counts[complement]
21
22    return pairs
23
24
25print(counted_pairs_with_sum([1, 5, 7, -1, 5], 6))
26# [(1, 5), (1, 5), (-1, 7)]

This version preserves multiplicity instead of collapsing everything into unique values.

Sorting Is a Good Alternative

If modifying or copying the input is acceptable, sorting plus a two-pointer scan is another strong option:

1def sorted_pairs_with_sum(values, target):
2    values = sorted(values)
3    left = 0
4    right = len(values) - 1
5    pairs = []
6
7    while left < right:
8        current = values[left] + values[right]
9        if current == target:
10            pairs.append((values[left], values[right]))
11            left += 1
12            right -= 1
13        elif current < target:
14            left += 1
15        else:
16            right -= 1
17
18    return pairs
19
20
21print(sorted_pairs_with_sum([1, 5, 7, -1, 5], 6))

This costs O(n log n) time because of sorting, but the scanning logic afterward is simple and space-efficient.

Decide What Counts as "All Pairs"

Before coding, settle the output contract:

• unique value pairs only
• all index pairs
• all value pairs respecting duplicates
• each pair ordered or unordered

These variations look similar in English but produce different code and different outputs. Many wrong answers come from solving a different version than the one the caller intended.

Common Pitfalls

• Forgetting to define whether duplicate values should generate repeated pairs.
• Returning both (1, 5) and (5, 1) when order is supposed to be irrelevant.
• Using an O(n^2) nested-loop solution when a hash-based solution would be simpler and faster.
• Sorting the array when the caller actually needed original index positions.
• Using a set and accidentally throwing away multiplicity that the problem needed to preserve.

Summary

• A hash-based scan is usually the best O(n) average-time solution.
• Clarify whether the result should contain unique value pairs or duplicate-respecting pairs.
• Use a frequency map when multiplicity matters.
• Use sorting and two pointers when a sorted approach is acceptable and index positions do not matter.
• The hardest part of the problem is often defining the exact output, not writing the loop.