Approximate Three Sum: Finding Three Numbers Closest to a Target

Approximate Three Sum

Imagine you have a bag of numbers. Someone gives you a *target* number, and asks you a question: "Pick any three numbers from the bag. Add them up. Which three give a sum that lands as close as possible to my target?"

That is exactly the Approximate Three Sum problem.

What the problem asks

You are given:

• An integer array called arr (just a list of whole numbers).
• A single number called target.

Your task: choose three numbers from arr, add them together, and find the combination whose sum is closest to target. You then return that sum — not the three numbers themselves, just their total.

Notice the word "closest." The sum does not have to equal the target exactly. It just needs to be nearer to the target than any other choice of three numbers.

A worked example

Example 1

Input:  arr = [2, 7, 11, 15], target = 3
Output: 20

Let's see why. We must pick three numbers out of these four. Here are the possible groups of three and their sums:

• 2 + 7 + 11 = 20
• 2 + 7 + 15 = 24
• 2 + 11 + 15 = 28
• 7 + 11 + 15 = 33

The target is 3. The sum closest to 3 is 20 (it is only 17 away, while every other choice is farther). So the answer is 20.

A helpful way to think about "closest" is distance. For any sum, the distance to the target is how far apart they are, ignoring the sign. In code we measure this with the absolute value: abs(sum - target). The smaller this distance, the better the choice.

Example 2

Input: arr = [-1, 2, 1, -4], target = 1

The same idea applies, and the numbers can be negative too. You would try the different groups of three, compute each sum, and keep the one whose distance to 1 is smallest.

One important guarantee

The problem tells you that each input has exactly one solution. That means you never have to worry about ties or about "no answer existing." There is always one clear best sum to return.

How to think about solving it

The most direct idea is to try every possible group of three numbers, compute each sum, and remember the sum that comes closest to the target.

1. Start by assuming the first group you see is the best so far.
2. Look at each new group of three. Compute its sum.
3. Compare its distance to the target (abs(sum - target)) with the best distance found so far.
4. If the new group is closer, it becomes the new best.
5. After checking all groups, return the best sum.

The starter code gives you the function shape to fill in:

class Solution {
public:
    int approximateThreeSum(vector<int> &arr,

Here vector<int> &arr is simply C++'s way of saying "a list of integers." Your job is to fill in the body so it returns the closest sum.