Three Sum: Finding All Triplets That Add Up to Zero

Three Sum: Finding Triplets That Add Up to Zero

Imagine you have a list of numbers, and someone asks you a simple question: "Can you find three numbers in this list that add up to exactly zero?" Not just one group — they want every possible group of three.

That is the Three Sum problem. Let's understand it step by step.

What the problem asks

You are given an array (a list) of whole numbers called arr. You must find all groups of three numbers from the array that satisfy two conditions:

1. The three numbers must come from three different positions in the array.
2. The three numbers must add up to 0.

In code terms, you pick three positions i, j, and k. The rule i != j, i != k, and j != k simply means all three positions must be different from each other. You are not allowed to use the same slot twice. Then the values at those positions must satisfy:

arr[i] + arr[j] + arr[k] == 0

Each valid group of three is called a triplet, written as [arr[i], arr[j], arr[k]]. You can return the triplets in any order — the order does not matter.

A worked example

Take this input:

arr = [-1, 0, 1, 2, -1, -4]

The answer is:

[[-1, -1, 2], [-1, 0, 1]]

Let's check why:

• -1 + -1 + 2 = 0 ✅ — the two -1 values come from two different spots in the array (position 0 and position 4), so this is allowed.
• -1 + 0 + 1 = 0 ✅
• What about a number like 2, -4, and something else? 2 + (-4) = -2, and there is no single number left that equals 2 to fix it up in a valid way, so no triplet there.

Notice something important: the two -1 values are at different positions, so using both is perfectly fine. The "different positions" rule is about slots in the array, not about the values being different.

The "no duplicates" rule

Here is the trickiest part. Look at this line:

> The solution set must not contain duplicate triplets.

This means the final list of answers must not repeat the same triplet twice. Two triplets count as the same if they contain the same numbers, even if those numbers were picked from different positions.

For example, with arr = [0, 0, 0]:

• Input: arr = [0, 0, 0]
• Output: [[0, 0, 0]]

There is only one triplet in the answer, even though there are three zeros you could pick from. Because [0, 0, 0] made from any choice of positions looks exactly the same, you list it only once.

So you must be careful to avoid reporting the same combination of values more than once.

How to think about solving it

A beginner's first idea is the brute force approach: try every possible group of three positions using three nested loops, and keep the ones that sum to zero. This works, but it is slow because it checks a huge number of combinations.

A smarter and very common approach is:

1. Sort the array first (arrange the numbers from smallest to largest).
2. Pick one number at a time as a "fixed" first value.
3. For the rest, use two pointers — one starting just after the fixed number and one at the end — moving them toward each other to find pairs that complete the sum to zero.
4. Sorting also makes it easy to skip duplicate values so you do not produce repeated triplets.

The function you fill in looks like this in C++:

vector<vector<int>> threeSum(vector<int> & arr)

It takes the array and returns a list of triplets, where each triplet is itself a small list of three integers.

Key takeaways

• A triplet is three numbers from three different positions in the array.
• Those three numbers must add up to 0.
• Same value at different positions is allowed; the same combination in the final answer is not.
• Sorting plus two pointers is the standard, efficient way to solve this.