# 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,

Input:

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

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.

Output:

## Java

Output:

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 Hashing –

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++

Output:

Quadruplet Found (4, 0, 7, 9)

## Java

Output:

Quadruplet Found (4, 0, 7, 9)

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 🙂

Get great deals at Amazon