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

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

Output:

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

Output:

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
avatar
Sort by:   newest | oldest | most voted
trackback

[…] is like a 2 sum problem. Keep notice of the index value, to avoid index out of bound error. Algo 2: Code  Time complexity: O(n^2). The idea is to consider every pair of elements in the array one by one […]

wpDiscuz