4 sum problem | Quadruplets with given sum

Given an unsorted array of integers, check if it contains four elements tuple (Quadruplets) having given sum.


For example,

arr = [ 2, 7, 4, 0, 9, 5, 1, 3 ]
sum = 20

Output: Quadruplet exists.

Below are Quadruplets with given sum 20

(0, 4, 7, 9)
(1, 3, 7, 9)
(2, 4, 5, 9)



1. Naive Recursive Approach –


The idea is similar to 0-1 Knapsack problem and uses recursion to solve this problem. For each item, we either consider current item or exclude it and recurse for remaining elements. We return true if we get desired sum by including or excluding current item.

C++ implementation –

Download   Run Code


Quadruplet Exists

We can also use four nested loops and consider every Quadruplet in given array to check if desired sum is found.



2. Efficient solution using Sorting –


The idea is to consider every pair of elements in the array one by one and insert it into a map. For each pair of element (i, j), we calculate the remaining sum. If remaining sum exists in the map and elements involved in previous occurrence don’t overlap with the current pair i.e. ((i, j, i, y) or (i, j, x, i) or (i, j, j, y) or (i, j, x, j)), we print the Quadruplet and return.

C++ implementation –

Download   Run Code


Quadruplet Found (4 0 7 9)

Print all distinct quadruplets present in an array

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of