The Four Sum Problem: Finding Groups of Four Numbers That Add Up to a Target

The Four Sum Problem

Imagine you have a row of numbers and a special "goal" number. Your job is to find every group of four numbers from the row that add up exactly to that goal. This is the Four Sum problem, and it builds on simpler ideas like adding two or three numbers to hit a target.

What we are given

We start with two things:

• An array arr of size n. An *array* is just a list of numbers laid out in a row, each one sitting at a numbered position called an index (the first position is index 0, the next is 1, and so on).
• An integer target. This is the goal number we want our four chosen numbers to add up to.

What we must find

We need to find all the unique quadruplets [arr[a], arr[b], arr[c], arr[d]]. A *quadruplet* is simply a group of four values. But not just any four — they must follow three rules:

1. 0 <= a, b, c, d < n — The four positions a, b, c, and d must all be valid spots inside the array (from index 0 up to the last index).
2. a, b, c, and d are distinct — The four positions must all be different. You cannot use the same slot twice. This is about the *positions*, not the values. (Two different positions are allowed to hold the same number.)
3. arr[a] + arr[b] + arr[c] + arr[d] = target — When you add up the four numbers at those positions, the sum must equal the goal.

One more thing: the answer can be returned in any order. The grader does not care which group comes first.

Walking through the example

Let's make this real with the example:

• Input: arr = [1, 0, -1, 0, -2, 2], target = 0
• Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Why these three groups? Check each one by adding them up:

• -2 + -1 + 1 + 2 = 0 ✓
• -2 + 0 + 0 + 2 = 0 ✓
• -1 + 0 + 0 + 1 = 0 ✓

Every group sums to 0, which is our target. Notice the second and third groups use two zeros. That is allowed, because the array [1, 0, -1, 0, -2, 2] actually has two separate 0 values sitting at different positions (index 1 and index 3). Using both of those is fine — they are different slots.

The meaning of "unique"

The word unique is important. We do not want the same group of values appearing twice in our answer. For example, [-2, -1, 1, 2] and [1, 2, -2, -1] contain the same four values, just shuffled. They count as one quadruplet, not two. So we only keep one copy of each distinct set of values.

The starting code

The problem gives us a function to fill in, written in C++:

using namespace std;
class Solution {
public:
    vector<vector<int>> fourSum(vector<int> &
    }
};

Here fourSum takes the array and the target and must return a vector<vector<int>> — that is a list of lists, where each inner list is one quadruplet of four numbers.

How to think about solving it

A beginner's first idea is brute force: try every possible group of four positions, add them up, and keep the ones that match. That works but is slow. The smarter approach usually sorts the array first, then loops over pairs of numbers and uses two pointers moving inward to find the remaining two. Sorting also makes it easy to skip duplicate values so the answer stays unique. The key takeaway for now is understanding *what* the problem asks: find all distinct sets of four numbers, at four different positions, that add up to the target.