Duplicate-Aware Two Sum: Finding All Unique Pairs

Duplicate-Aware Two Sum

Imagine you have a row of numbered cards laid out on a table, and a friend gives you a "magic number" called the target. Your job is to find every pair of cards that, when added together, equal that target. This is the classic *Two Sum* problem — but with one extra twist that makes it interesting.

The Problem

You are given:

• An array of integers called arr (just a list of numbers).
• A single integer called target (the sum you are aiming for).

You must write a function that finds two numbers in the array that add up to the target. There can be more than one such pair, so you return all of them. If no pair adds up to the target, you return an empty array (a list with nothing inside). The order in which you return the pairs does not matter.

A Worked Example

Let's use the example:

arr = [1, 2, 2, 3, 4, 5], target = 6

We look for any two numbers that add up to 6:

• 1 + 5 = 6 ✅ → the pair [1, 5]
• 2 + 4 = 6 ✅ → the pair [2, 4]
• 3 + 3 = 6? There is only one 3 in the array, so we cannot use it twice. ❌

So the answer is:

[[1, 5], [2, 4]]

The "Duplicate-Aware" Twist

Look closely at the array: the number 2 appears twice. That is why this problem is called *duplicate-aware*.

The important rule is:

> You must not return the same pair more than once. All pairs must be unique.

Since there are two 2s, you might be tempted to report [2, 4] twice — once for each 2. But the answer should list [2, 4] only once. Two pairs count as "the same" when they contain the same two values, even if they came from different positions in the array.

Think of it like making a guest list: if two people have the exact same name and they both pair up with the same partner, you still write that couple down only once.

What You Need to Build

The starting code gives you a function to fill in:

using namespace std;
class Solution {
public:
    vector<vector<int>> duplicateAwareTwoSum(
        vector<int> &arr, int target ) {

    }
};

A few things to notice:

• The return type is vector<vector<int>>. In plain words, this is a *list of pairs* — each inner list holds the two numbers of one pair.
• arr is passed by reference (the &), which simply means the function works directly with the given array.

How to Think About Solving It

A clear plan is:

1. Go through the numbers and, for each one, check whether target - number also exists in the array.
2. When you find a match, you have a valid pair.
3. Before saving the pair, make sure you have not already saved that same pair. This is the duplicate-aware step.

To keep pairs unique, a handy trick is to always store each pair in a fixed order (for example, the smaller number first), so [2, 4] and [4, 2] are recognized as the same thing. You can use a set or a "seen" record to remember which pairs you have already added.

The key lesson here is not just finding sums — it is learning to handle repeated values carefully so your answer stays clean and contains no duplicates.