Given an integer array arr[] and an integer target, find the sum of triplets such that the sum is closest to target.
Note: If there are multiple sums closest to target, print the maximum one.
Examples:
Input: arr[] = [-1, 2, 2, 4], target = 4
Output: 5
Explanation: All possible triplets
[-1, 2, 2], sum = (-1) + 2 + 2 = 3
[-1, 2, 4], sum = (-1) + 2 + 4 = 5
[-1, 2, 4], sum = (-1) + 2 + 4 = 5
[2, 2, 4], sum = 2 + 2 + 4 = 8
Triplet [-1, 2, 2], [-1, 2, 4] and [-1, 2, 4] have sum closest to target, so return the maximum one, that is 5.Input: arr[] = [1, 10, 4, 5], target = 10
Output: 10
Explanation: All possible triplets
[1, 10, 4], sum = (1 + 10 + 4) = 15
[1, 10, 5], sum = (1 + 10 + 5) = 16
[1, 4, 5], sum = (1 + 4 + 5) = 10
[10, 4, 5], sum = (10 + 4 + 5) = 19
Triplet [1, 4, 5] has sum = 10 which is closest to target.
Try it on GfG Practice
Table of Content
[Naive Approach] Explore all Subsets of Size 3 - O(n^3) Time and O(1) Space
The naive approach is to explore all subsets of size three and keep a track of the difference between target and the sum of the subset. Then, return the sum which is closest to target.
#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;
int closest3Sum(vector<int> &arr, int target) {
int n = arr.size();
int minDiff = INT_MAX;
int res = 0;
// Generating all possible triplets
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
int currSum = arr[i] + arr[j] + arr[k];
int currDiff = abs(currSum - target);
// if currentDiff is less than minDiff, it indicates
// that this triplet is closer to the target
if (currDiff < minDiff) {
res = currSum;
minDiff = currDiff;
}
// If multiple sums are closest, take maximum one
else if(currDiff == minDiff) {
res = max(res, currSum);
}
}
}
}
return res;
}
int main() {
vector<int> arr = {-1, 2, 2, 4};
int target = 4;
cout << closest3Sum(arr, target);
return 0;
}
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
int closest3Sum(int arr[], int n, int target) {
int minDiff = INT_MAX;
int res = 0;
// Generating all possible triplets
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
int currSum = arr[i] + arr[j] + arr[k];
int currDiff = abs(currSum - target);
// if currentDiff is less than minDiff, it indicates
// that this triplet is closer to the target
if (currDiff < minDiff) {
res = currSum;
minDiff = currDiff;
}
// If multiple sums are closest, take maximum one
else if(currDiff == minDiff && res < currSum) {
res = currSum;
}
}
}
}
return res;
}
int main() {
int arr[] = {-1, 2, 2, 4};
int target = 4;
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", closest3Sum(arr, n, target));
return 0;
}
class GfG {
static int closest3Sum(int[] arr, int target) {
int n = arr.length;
int minDiff = Integer.MAX_VALUE;
int res = 0;
// Generating all possible triplets
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
int currSum = arr[i] + arr[j] + arr[k];
int currDiff = Math.abs(currSum - target);
// if currentDiff is less than minDiff, it indicates
// that this triplet is closer to the target
if (currDiff < minDiff) {
res = currSum;
minDiff = currDiff;
}
// If multiple sums are closest, take maximum one
else if(currDiff == minDiff) {
res = Math.max(res, currSum);
}
}
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {-1, 2, 2, 4};
int target = 4;
System.out.println(closest3Sum(arr, target));
}
}
def closest3Sum(arr, target):
n = len(arr)
minDiff = float('inf')
res = 0
# Generating all possible triplets
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
currSum = arr[i] + arr[j] + arr[k]
currDiff = abs(currSum - target)
# if currentDiff is less than minDiff, it indicates
# that this triplet is closer to the target
if currDiff < minDiff:
res = currSum
minDiff = currDiff
# If multiple sums are closest, take maximum one
elif currDiff == minDiff:
res = max(res, currSum)
return res
if __name__ == "__main__":
arr = [-1, 2, 2, 4]
target = 4
print(closest3Sum(arr, target))
using System;
class GfG {
static int closest3Sum(int[] arr, int target) {
int n = arr.Length;
int minDiff = int.MaxValue;
int res = 0;
// Generating all possible triplets
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
int currSum = arr[i] + arr[j] + arr[k];
int currDiff = Math.Abs(currSum - target);
// if currentDiff is less than minDiff, it indicates
// that this triplet is closer to the target
if (currDiff < minDiff) {
res = currSum;
minDiff = currDiff;
}
// If multiple sums are closest, take maximum one
else if(currDiff == minDiff) {
res = Math.Max(res, currSum);
}
}
}
}
return res;
}
static void Main() {
int[] arr = {-1, 2, 2, 4};
int target = 4;
Console.WriteLine(closest3Sum(arr, target));
}
}
function closest3Sum(arr, target) {
let n = arr.length;
let minDiff = Number.MAX_VALUE;
let res = 0;
// Generating all possible triplets
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
let currSum = arr[i] + arr[j] + arr[k];
let currDiff = Math.abs(currSum - target);
// if currentDiff is less than minDiff, it indicates
// that this triplet is closer to the target
if (currDiff < minDiff) {
res = currSum;
minDiff = currDiff;
}
// If multiple sums are closest, take maximum one
else if(currDiff == minDiff) {
res = Math.max(res, currSum);
}
}
}
}
return res;
}
// Driver Code
let arr = [-1, 2, 2, 4];
let target = 4;
console.log(closest3Sum(arr, target));
Output
5
[Expected Approach] Sorting and Two Pointers – O(n^2) Time and O(1) Space
Sort the array and fix one element. For the remaining part, use two pointers one at the start and one at the end to find the closest sum. Compare each triplet’s sum with the target and update the closest value. If the sum is smaller than the target, move the left pointer right; if larger, move the right pointer left. If the sum equals the target, it’s the closest possible.
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int closest3Sum(vector<int> &arr, int target) {
int n = arr.size();
sort(arr.begin(), arr.end());
int res = 0;
int minDiff = INT_MAX;
for (int i = 0; i < n - 2; i++) {
// Initialize the left and right pointers
int l = i + 1, r = n - 1;
while (l < r) {
int currSum = arr[i] + arr[l] + arr[r];
// If |currSum - target| < minDiff, then we have
// found a triplet which is closer to target
if (abs(currSum - target) < minDiff) {
minDiff = abs(currSum - target);
res = currSum;
}
// If multiple sums are closest, take maximum one
else if(abs(currSum - target) == minDiff) {
res = max(res, currSum);
}
// If currSum > target then we will decrease the
// right pointer to move closer to target
if (currSum > target)
r--;
// If currSum >= target then we will increase the
// left pointer to move closer to target
else
l++;
}
}
return res;
}
int main() {
vector<int> arr = {-1, 2, 2, 4};
int target = 4;
cout << closest3Sum(arr, target);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Function to compare integers for qsort
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int closest3Sum(int arr[], int n, int target) {
qsort(arr, n, sizeof(int), compare);
int res = 0;
int minDiff = INT_MAX;
for (int i = 0; i < n - 2; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
int currSum = arr[i] + arr[l] + arr[r];
// If |currSum - target| < minDiff, then we have
// found a triplet which is closer to target
if (abs(currSum - target) < minDiff) {
minDiff = abs(currSum - target);
res = currSum;
}
// If multiple sums are closest, take maximum one
else if(abs(currSum - target) == minDiff) {
if(res < currSum)
res = currSum;
}
// If currSum > target then we will decrease the
// right pointer to move closer to target
if (currSum > target)
r--;
// If currSum <= target then we will increase the
// left pointer to move closer to target
else
l++;
}
}
return res;
}
int main() {
int arr[] = {-1, 2, 2, 4};
int target = 4;
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", closest3Sum(arr, n, target));
return 0;
}
import java.util.*;
class GfG {
static int closest3Sum(int[] arr, int target) {
int n = arr.length;
Arrays.sort(arr);
int res = 0;
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < n - 2; i++) {
// Initialize the left and right pointers
int l = i + 1, r = n - 1;
while (l < r) {
int currSum = arr[i] + arr[l] + arr[r];
// If |currSum - target| < minDiff, then we have
// found a triplet which is closer to target
if (Math.abs(currSum - target) < minDiff) {
minDiff = Math.abs(currSum - target);
res = currSum;
}
// If multiple sums are closest, take maximum one
else if(Math.abs(currSum - target) == minDiff) {
res = Math.max(res, currSum);
}
// If currSum > target then we will decrease the
// right pointer to move closer to target
if (currSum > target)
r--;
// If currSum <= target then we will increase the
// left pointer to move closer to target
else
l++;
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {-1, 2, 2, 4};
int target = 4;
System.out.println(closest3Sum(arr, target));
}
}
def closest3Sum(arr, target):
n = len(arr)
arr.sort()
res = 0
minDiff = float('inf')
for i in range(n - 2):
# Initialize the left and right pointers
l, r = i + 1, n - 1
while l < r:
currSum = arr[i] + arr[l] + arr[r]
# If |currSum - target| < minDiff, then we have
# found a triplet which is closer to target
if abs(currSum - target) < minDiff:
minDiff = abs(currSum - target)
res = currSum
# If multiple sums are closest, take maximum one
elif abs(currSum - target) == minDiff:
res = max(res, currSum)
# If currSum > target then we will decrease the
# right pointer to move closer to target
if currSum > target:
r -= 1
# If currSum <= target then we will increase the
# left pointer to move closer to target
else:
l += 1
return res
if __name__ == "__main__":
arr = [-1, 2, 2, 4]
target = 4
print(closest3Sum(arr, target))
using System;
class GfG {
static int closest3Sum(int[] arr, int target) {
int n = arr.Length;
Array.Sort(arr);
int res = 0;
int minDiff = int.MaxValue;
for (int i = 0; i < n - 2; i++) {
// Initialize the left and right pointers
int l = i + 1, r = n - 1;
while (l < r) {
int currSum = arr[i] + arr[l] + arr[r];
// If |currSum - target| < minDiff, then we have
// found a triplet which is closer to target
if (Math.Abs(currSum - target) < minDiff) {
minDiff = Math.Abs(currSum - target);
res = currSum;
}
// If multiple sums are closest, take maximum one
else if(Math.Abs(currSum - target) == minDiff) {
res = Math.Max(res, currSum);
}
// If currSum > target then we will decrease the
// right pointer to move closer to target
if (currSum > target)
r--;
// If currSum <= target then we will increase the
// left pointer to move closer to target
else
l++;
}
}
return res;
}
static void Main() {
int[] arr = { -1, 2, 2, 4 };
int target = 4;
Console.WriteLine(closest3Sum(arr, target));
}
}
function closest3Sum(arr, target) {
let n = arr.length;
arr.sort((a, b) => a - b);
let res = 0;
let minDiff = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < n - 2; i++) {
// Initialize the left and right pointers
let l = i + 1, r = n - 1;
while (l < r) {
let currSum = arr[i] + arr[l] + arr[r];
// If |currSum - target| < minDiff, then we have
// found a triplet which is closer to target
if (Math.abs(currSum - target) < minDiff) {
minDiff = Math.abs(currSum - target);
res = currSum;
}
// If multiple sums are closest, take maximum one
else if(Math.abs(currSum - target) == minDiff) {
res = Math.max(res, currSum);
}
// If currSum > target then we will decrease the
// right pointer to move closer to target
if (currSum > target)
r--;
// If currSum <= target then we will increase the
// left pointer to move closer to target
else
l++;
}
}
return res;
}
// Driver Code
let arr = [-1, 2, 2, 4];
let target = 4;
console.log(closest3Sum(arr, target));
Output
5