4 Sum - Quadruplet Sum Closest to Target

Last Updated : 23 Jul, 2025

Given an array arr[] of n integers and an integer target, the task is to find a quadruplet in arr[] whose sum is closest to target.

Note: There may be multiple quadruplets with sum closest to the target, return any one of them.

Examples:

Input: arr[] = {4, 5, 3, 4, 1, 2}, target = 13
Output: {4, 5, 3, 1}
Explanation:
Sum of quadruplets:
4 + 5 + 3 + 4 = 16
4 + 5 + 3 + 1 = 13
4 + 5 + 3 + 2 = 14
5 + 3 + 4 + 4 = 16
....
Quadruplet having sum 13 is closest to the target.
Input: arr[] = {1, 2, 3, 4, 10}, target = 20
Output: {1, 3, 5, 10}
Explanation:
Sum of quadruplets:
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 10 = 16
2 + 3 + 4 + 10 = 19
1 + 3 + 4 + 10 = 18
...
Quadruplet having sum 19 is closest to the target.

Table of Content

[Naive Approach] Explore all subsets of size four - O(n^4) Time and O(1) Space
[Expected Approach] Sorting and Two Pointers – O(n^3) time and O(1) space

[Naive Approach] Explore all subsets of size four - O(n^4) Time and O(1) Space

The idea is to generate all possible quadruplets using four nested loops and keep track of the smallest difference between target and the sum of each quadruplet. Then, return the quadruplet with the minimum difference between its sum and target.

C++

// C++ program to find the quadruplet with
// closest sum by exploring all quadruplets

#include <bits/stdc++.h>
using namespace std;

vector<int> findQuadruplet(vector<int> &arr, int target) {
    int n = arr.size();

    vector<int> res;
    int minDiff = INT_MAX;

    // Generating all possible quadruplets
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                for (int l = k + 1; l < n; l++) {
                    int currSum = arr[i] + arr[j] + arr[k] + arr[l];
                    int currDiff = abs(currSum - target);

                    // if currDiff is less than minDiff, then this
                    // quadruplet is closer to the target
                    if (currDiff < minDiff) {
                        minDiff = currDiff;
                        res = {arr[i], arr[j], arr[k], arr[l]};
                    }
                }
            }
        }
    }

    return res;
}

int main() {
    vector<int> arr = {4, 5, 3, 4, 1, 2};
    int target = 13;

    vector<int> res = findQuadruplet(arr, target);
    cout << res[0] << " " << res[1] << " " << res[2] << " " << res[3];

    return 0;
}

// C program to find the quadruplet with 
// closest sum by exploring all quadruplets

#include <stdio.h>
#include <limits.h>

int* findQuadruplet(int arr[], int n, int target) {
    int minDiff = INT_MAX;
    int* res = (int*)malloc(4 * sizeof(int));

    // Generating all possible quadruplets
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                for (int l = k + 1; l < n; l++) {
                    int currSum = arr[i] + arr[j] + arr[k] + arr[l];
                    int currDiff = abs(currSum - target);

                    // if currDiff is less than minDiff, then this
                    // quadruplet is closer to the target
                    if (currDiff < minDiff) {
                        minDiff = currDiff;
                        res[0] = arr[i];
                        res[1] = arr[j];
                        res[2] = arr[k];
                        res[3] = arr[l];
                    }
                }
            }
        }
    }
    
    return res;
}

int main() {
    int arr[] = {4, 5, 3, 4, 1, 2};
    int target = 13;

    int* res = findQuadruplet(arr, sizeof(arr)/sizeof(arr[0]), target);
    printf("%d %d %d %d\n", res[0], res[1], res[2], res[3]);
    return 0;
}

Java

// Java program to find the quadruplet with 
// closest sum by exploring all quadruplets

import java.util.ArrayList;
import java.util.List;

class GfG {

    static List<Integer> findQuadruplet(int[] arr, int target) {
        int n = arr.length;

        List<Integer> res = new ArrayList<>();
        int minDiff = Integer.MAX_VALUE;

        // Generating all possible quadruplets
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int currSum = arr[i] + arr[j] + arr[k] + arr[l];
                        int currDiff = Math.abs(currSum - target);

                        // if currDiff is less than minDiff, then this
                        // quadruplet is closer to the target
                        if (currDiff < minDiff) {
                            minDiff = currDiff;
                            res.clear();
                            res.add(arr[i]);
                            res.add(arr[j]);
                            res.add(arr[k]);
                            res.add(arr[l]);
                        }
                    }
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 3, 4, 1, 2};
        int target = 13;

        List<Integer> res = findQuadruplet(arr, target);
        for (int i = 0; i < res.size(); i++)
            System.out.print(res.get(i) + " ");
    }
}

Python

# Python program to find the quadruplet with 
# closest sum by exploring all quadruplets

def findQuadruplet(arr, target):
    n = len(arr)

    res = []
    minDiff = float('inf')

    # Generating all possible quadruplets
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            for k in range(j + 1, n - 1):
                for l in range(k + 1, n):
                    currSum = arr[i] + arr[j] + arr[k] + arr[l]
                    currDiff = abs(currSum - target)

                    # if currDiff is less than minDiff, then this
                    # quadruplet is closer to the target
                    if currDiff < minDiff:
                        minDiff = currDiff
                        res = [arr[i], arr[j], arr[k], arr[l]]

    return res

if __name__ == "__main__":
    arr = [4, 5, 3, 4, 1, 2]
    target = 13

    res = findQuadruplet(arr, target)
    print(res[0], res[1], res[2], res[3])

// C# program to find the quadruplet with 
// closest sum by exploring all quadruplets

using System;
using System.Collections.Generic;

class GfG {
    static List<int> findQuadruplet(int[] arr, int target) {
        int n = arr.Length;

        List<int> res = new List<int>();
        int minDiff = int.MaxValue;

        // Generating all possible quadruplets
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int currSum = arr[i] + arr[j] + arr[k] + arr[l];
                        int currDiff = Math.Abs(currSum - target);

                        // if currDiff is less than minDiff, then this
                        // quadruplet is closer to the target
                        if (currDiff < minDiff) {
                            minDiff = currDiff;
                            res = new List<int> { arr[i], arr[j], arr[k], arr[l] };
                        }
                    }
                }
            }
        }

        return res;
    }

    static void Main(string[] args) {
        int[] arr = { 4, 5, 3, 4, 1, 2 };
        int target = 13;

        List<int> res = findQuadruplet(arr, target);
        Console.WriteLine($"{res[0]} {res[1]} {res[2]} {res[3]}");
    }
}

JavaScript

// JavaScript program to find the quadruplet with 
// closest sum by exploring all quadruplets

function findQuadruplet(arr, target) {
    let n = arr.length;

    let res = [];
    let minDiff = Number.MAX_VALUE;

    // Generating all possible quadruplets
    for (let i = 0; i < n - 3; i++) {
        for (let j = i + 1; j < n - 2; j++) {
            for (let k = j + 1; k < n - 1; k++) {
                for (let l = k + 1; l < n; l++) {
                    let currSum = arr[i] + arr[j] + arr[k] + arr[l];
                    let currDiff = Math.abs(currSum - target);

                    // if currDiff is less than minDiff, then this
                    // quadruplet is closer to the target
                    if (currDiff < minDiff) {
                        minDiff = currDiff;
                        res = [arr[i], arr[j], arr[k], arr[l]];
                    }
                }
            }
        }
    }

    return res;
}

const arr = [4, 5, 3, 4, 1, 2];
const target = 13;

const res = findQuadruplet(arr, target);
console.log(res[0], res[1], res[2], res[3]);

Output

4 5 3 1

[Expected Approach] Sorting and Two Pointers – O(n^3) time and O(1) space

Initially, we sort the input array so that we can apply two pointers technique. Then, we fix the first two elements of the quadruplet using two nested loops and inside the second nested loop we use two pointers technique to find the remaining two elements. Set one pointer at the beginning (left) and another at the end (right) of the remaining array. We then find the absolute difference between the sum of all these four elements and target and store the quadruple having minimum absolute difference.
If sum < target, move left pointer towards right to increase the sum.
If sum > target, move right pointer towards left to decrease the sum.
If sum == target, we’ve found the quadruplet with sum = target, therefore this is the quadruplet with closest sum.

C++

// C++ program to find the quadruplet with closest sum 
// using Two Pointers Technique

#include <bits/stdc++.h>
using namespace std;

vector<int> findQuadruplet(vector<int> &arr, int target) {
    int n = arr.size();

    // Sorting the array so that we can use
    // two pointers technique
    sort(arr.begin(), arr.end());
    vector<int> res(4);
    int minDiff = INT_MAX;

    for (int i = 0; i < n - 3; i++) {
        for (int j = 0; j < n - 2; j++) {
            int l = j + 1, r = n - 1;

            while (l < r) {
                int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                // If |currSum - target| < minDiff, then we have 
                // found a quadruplet which is closer to target
                if (abs(currSum - target) < minDiff) {
                    minDiff = abs(currSum - target);
                    res = {arr[i], arr[j], arr[l], arr[r]};
                }

                // 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 = {4, 5, 3, 4, 1, 2};
    int target = 13;

    vector<int> res = findQuadruplet(arr, target);
    cout << res[0] << " " << res[1] << " " << res[2] << " " << res[3];

    return 0;
}

// C program to find the quadruplet with
// closest sum using Two Pointers Technique

#include <stdio.h>
#include <limits.h>

// Function to compare two integers for qsort
int compare(const int* a, const int* b) {
    return (*a - *b);
}

// Function to sort the array using qsort
void sort(int* arr, int n) {
    qsort(arr, n, sizeof(int), (int (*)(const void *, const void *))compare);
}

// Function to find the quadruplet with the closest sum
int* findQuadruplet(int* arr, int n, int target) {
    
    // Sorting the array so that we can use
    // two pointers technique
    sort(arr, n);
    int minDiff = INT_MAX;
    int* res = (int*)malloc(4 * sizeof(int));

    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            int l = j + 1, r = n - 1;

            while (l < r) {
                int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                // If |currSum - target| < minDiff, then we have found a
                // quadruplet which is closer to target
                if (abs(currSum - target) < minDiff) {
                    minDiff = abs(currSum - target);
                    res[0] = arr[i];
                    res[1] = arr[j];
                    res[2] = arr[l];
                    res[3] = arr[r];
                }

                // 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[] = {4, 5, 3, 4, 1, 2};
    int target = 13;

    int* res = findQuadruplet(arr, sizeof(arr) / sizeof(arr[0]), target);
    printf("%d %d %d %d\n", res[0], res[1], res[2], res[3]);
    return 0;
}

Java

// Java program to find the quadruplet with
// closest sum using Two Pointers Technique

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class GfG {

    static List<Integer> findQuadruplet(int[] arr, int target) {
        int n = arr.length;

        // Sorting the array so that we can use
        // two pointers technique
        Arrays.sort(arr);
        List<Integer> res = new ArrayList<>();
        int minDiff = Integer.MAX_VALUE;

        for (int i = 0; i < n - 3; i++) {
            for (int j = 0; j < n - 2; j++) {
                int l = j + 1, r = n - 1;

                while (l < r) {
                    int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                    // If |currSum - target| < minDiff, then we have 
                    // found a quadruplet which is closer to target
                    if (Math.abs(currSum - target) < minDiff) {
                        minDiff = Math.abs(currSum - target);
                        res.clear();
                        res.add(arr[i]);
                        res.add(arr[j]);
                        res.add(arr[l]);
                        res.add(arr[r]);
                    }

                    // 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 = {4, 5, 3, 4, 1, 2};
        int target = 13;

        List<Integer> res = findQuadruplet(arr, target);
        for (int i = 0; i < res.size(); i++) 
            System.out.print(res.get(i) + " ");
    }
}

Python

# Python program to find the quadruplet with
# closest sum using Two Pointers Technique

def findQuadruplet(arr, target):
    n = len(arr)

    # Sorting the array so that we can use
    # two pointers technique
    arr.sort()
    res = [0] * 4
    minDiff = float('inf')

    for i in range(n - 3):
        for j in range(n - 2):
            l = j + 1
            r = n - 1

            while l < r:
                currSum = arr[i] + arr[j] + arr[l] + arr[r]

                # If |currSum - target| < minDiff, then we have 
                # found a quadruplet which is closer to target
                if abs(currSum - target) < minDiff:
                    minDiff = abs(currSum - target)
                    res = [arr[i], arr[j], arr[l], arr[r]]

                # 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 = [4, 5, 3, 4, 1, 2]
    target = 13

    res = findQuadruplet(arr, target)
    print(res[0], res[1], res[2], res[3])

// C# program to find the quadruplet with
// closest sum using Two Pointers Technique

using System;
using System.Collections.Generic;

class GfG {
    static List<int> findQuadruplet(List<int> arr, int target) {
        int n = arr.Count;

        // Sorting the array so that we can use
        // two pointers technique
        arr.Sort();
        List<int> res = new List<int>(4);
        int minDiff = int.MaxValue;

        for (int i = 0; i < n - 3; i++) {
            for (int j = 0; j < n - 2; j++) {
                int l = j + 1, r = n - 1;

                while (l < r) {
                    int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                    // If |currSum - target| < minDiff, then we have 
                    // found a quadruplet which is closer to target
                    if (Math.Abs(currSum - target) < minDiff) {
                        minDiff = Math.Abs(currSum - target);
                        res = new List<int> { arr[i], arr[j], arr[l], arr[r] };
                    }

                    // 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(string[] args) {
        List<int> arr = new List<int> { 4, 5, 3, 4, 1, 2 };
        int target = 13;

        List<int> res = findQuadruplet(arr, target);
        Console.WriteLine($"{res[0]} {res[1]} {res[2]} {res[3]}");
    }
}

JavaScript

// JavaScript program to find the quadruplet with
// closest sum using Two Pointers Technique

function findQuadruplet(arr, target) {
    const n = arr.length;

    // Sorting the array so that we can use
    // two pointers technique
    arr.sort((a, b) => a - b);
    let res = new Array(4);
    let minDiff = Number.MAX_VALUE;

    for (let i = 0; i < n - 3; i++) {
        for (let j = 0; j < n - 2; j++) {
            let l = j + 1, r = n - 1;

            while (l < r) {
                let currSum = arr[i] + arr[j] + arr[l] + arr[r];

                // If |currSum - target| < minDiff, then we have 
                // found a quadruplet which is closer to target
                if (Math.abs(currSum - target) < minDiff) {
                    minDiff = Math.abs(currSum - target);
                    res = [arr[i], arr[j], arr[l], arr[r]];
                }

                // 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;
}

const arr = [4, 5, 3, 4, 1, 2];
const target = 13;

const res = findQuadruplet(arr, target);
console.log(res[0], res[1], res[2], res[3]);

Output

1 3 4 5

amitja57a

Improve

Article Tags :

4 Sum - Quadruplet Sum Closest to Target

[Naive Approach] Explore all subsets of size four - O(n^4) Time and O(1) Space

[Expected Approach] Sorting and Two Pointers – O(n^3) time and O(1) space

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

Thank You!

What kind of Experience do you want to share?