Print all quadruplets with given sum | 4-sum problem extended

Given an unsorted array of integers, print all distinct four elements tuple (Quadruplets) in it having given sum.

 

For example,


Input:
A[] = [ 2, 7, 4, 0, 9, 5, 1, 3 ]
sum = 20

Output: Below are the quadruplets with sum 20

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

 


 

In previous post, we have discussed how to check if an array contains a quadruplet or not. In this post, we will print all distinct quadruplets present in an array.
 

We start by sorting the given array in ascending order and then for each pair (A[i], A[j]) in the array where (i < j), we check if a quadruplet is formed by current pair and a pair from sub-array A[j+1..n). Refer this post to find pairs with given sum in a sorted array in linear time.

 
C++ implementation –
 

Download   Run Code

Output:

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

 
The time complexity of above solution is O(n3) and auxiliary space used by the program is O(1).

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

Can’t you reuse the code (second part) in https://www.techiedelight.com/4-sum-problem/? Instead of return true when finding quadruplet, you keep printing it until the loop is over. That way you have time O(n^2) and space O(n).

wpDiscuz