Given an unsorted array of integers, print all distinct four elements tuple (Quadruplets) in it having given sum.
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <algorithm> using namespace std; // Function to print all Quadruplet present in an array with given sum void quadTuple(int arr[], int n, int sum) { // sort the array in ascending order sort (arr, arr + n); // check if Quadruplet is formed by arr[i], arr[j] and a pair from // sub-array arr[j+1..n) for (int i = 0; i <= n - 4; i++) { for (int j = i + 1; j <= n - 3; j++) { // k stores remaining sum int k = sum - (arr[i] + arr[j]); // check for sum k in sub-array arr[j+1..n) int low = j + 1, high = n - 1; while (low < high) { if (arr[low] + arr[high] < k) low++; else if (arr[low] + arr[high] > k) high--; // Quadruplet with given sum found else { cout << "(" << arr[i] << " " << arr[j] << " " << arr[low] << " " << arr[high] << ")\n"; low++, high--; } } } } } // main function int main() { int arr[] = { 2, 7, 4, 0, 9, 5, 1, 3 }; int sum = 20; int n = sizeof(arr) / sizeof(arr[0]); quadTuple(arr, n, sum); return 0; } |
Output:
(0 4 7 9)
(1 3 7 9)
(2 4 5 9)
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import java.util.Arrays; class Quadruplets { // Function to print all Quadruplet present in an array with given sum public static void quadTuple(int[] A, int sum) { // sort the array in ascending order Arrays.sort(A); // check if Quadruplet is formed by A[i], A[j] and a pair from // sub-array A[j+1..n) for (int i = 0; i <= A.length - 4; i++) { for (int j = i + 1; j <= A.length - 3; j++) { // k stores remaining sum int k = sum - (A[i] + A[j]); // check for sum k in sub-array A[j+1..n) int low = j + 1, high = A.length - 1; while (low < high) { if (A[low] + A[high] < k) { low++; } else if (A[low] + A[high] > k) { high--; } // Quadruplet with given sum found else { System.out.println("(" + A[i] + " " + A[j] + " " + A[low] + " " + A[high] + ")"); low++; high--; } } } } } // main function public static void main(String[] args) { int[] A = { 2, 7, 4, 0, 9, 5, 1, 3 }; int sum = 20; quadTuple(A, sum); } } |
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).
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
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).
Charles, we can do that way as well but it won’t return distinct pairs. Initially, we also had that solution in mind but it didn’t work out. Please check – https://ideone.com/fwzL2O
This is another solution with O(n^3) complexity
public static printQuadruplets(int a[], int quadrletsSum, int[] quadrlets, int quadrletCount, int totalCount, int totalSum) {
for (int i = 0; i 1){
if(quadrlets + a[i] < totalSum ){
quadrlets[quadrletCount] = a[i];
printQuadruplets(a, quadrlets, quadrlets, quadrletCount + 1, totalCount, totalSum);
}
} if(totalCount – quadrletsCount == 1){
if(quadrlets + a[i] = totalSum ){
quadrlets[quadrletCount] = a[i];
print quadrlets;
}
}
}
}