Given an array arr of integers of size N and a target number, the task is to find all unique quadruplets in it, whose sum is equal to the target number. Examples:
Input: arr[] = {4, 1, 2, -1, 1, -3], target = 1 Output: [[-3, -1, 1, 4], [-3, 1, 1, 2]] Explanation: Both the quadruplets sum equals to target. Input: arr[] = {2, 0, -1, 1, -2, 2}, target = 2 Output: [[-2, 0, 2, 2], [-1, 0, 1, 2]]
Two-Pointers approach: This problem follows the Two Pointers pattern and shares similarities with Triplet Sum to Zero. We can follow a similar approach to iterate through the array, taking one number at a time. At every step during the iteration, we will search for the quadruplets similar to Triplet Sum to Zero whose sum is equal to the given target.
C++
// C++ program to find four// elements that sum to a given value#include <bits/stdc++.h>using namespace std;class QuadrupleSumToTarget {public: // Function to find quadruplets static vector<vector<int> > searchQuadruplets( vector<int>& arr, int target) { sort(arr.begin(), arr.end()); vector<vector<int> > quadruplets; for (int i = 0; i < arr.size() - 3; i++) { if (i > 0 && arr[i] == arr[i - 1]) { // Skip same element // to avoid duplicate continue; } for (int j = i + 1; j < arr.size() - 2; j++) { if (j > i + 1 && arr[j] == arr[j - 1]) { // Skip same element // to avoid duplicate quad continue; } searchPairs( arr, target, i, j, quadruplets); } } return quadruplets; }private: // Function to search Quadruplets static void searchPairs( const vector<int>& arr, int targetSum, int first, int second, vector<vector<int> >& quadruplets) { int left = second + 1; int right = arr.size() - 1; while (left < right) { int sum = arr[first] + arr[second] + arr[left] + arr[right]; if (sum == targetSum) { // Found the quadruplet quadruplets .push_back( { arr[first], arr[second], arr[left], arr[right] }); left++; right--; // Skip same element to avoid // duplicate quadruplets while (left < right && arr[left] == arr[left - 1]) { left++; } // Skip same element to avoid // duplicate quadruplets while (left < right && arr[right] == arr[right + 1]) { right--; } } // We need a pair // with a bigger sum else if (sum < targetSum) { left++; } // We need a pair // with a smaller sum else { right--; } } }};void printQuad( vector<int>& vec, int target){ // Function call auto result = QuadrupleSumToTarget:: searchQuadruplets( vec, target); // Print Quadruples for (int j = 0; j < result.size(); j++) { vector<int> vec = result[j]; if (j == 0) cout << "["; for (int i = 0; i < vec.size(); i++) { if (i == 0) cout << "["; cout << vec[i]; if (i != vec.size() - 1) cout << ", "; else cout << "]"; } if (j != result.size() - 1) cout << ", "; else cout << "]"; }}// Driver codeint main(int argc, char* argv[]){ vector<int> vec = { 4, 1, 2, -1, 1, -3 }; int target = 1; printQuad(vec, target); return 0;} |
Java
import java.util.ArrayList;import java.util.Arrays;import java.util.List;class QuadrupleSumToTarget {// Function to find quadrupletspublic static List<List<Integer>> searchQuadruplets(int[] arr, int target) {Arrays.sort(arr);List<List<Integer>> quadruplets = new ArrayList<>(); for (int i = 0; i < arr.length - 3; i++) { if (i > 0 && arr[i] == arr[i - 1]) { // Skip same element to avoid duplicate continue; } for (int j = i + 1; j < arr.length - 2; j++) { if (j > i + 1 && arr[j] == arr[j - 1]) { // Skip same element to avoid duplicate quad continue; } searchPairs(arr, target, i, j, quadruplets); } } return quadruplets;}// Function to search Quadrupletsprivate static void searchPairs(int[] arr, int targetSum, int first, int second, List<List<Integer>> quadruplets) { int left = second + 1; int right = arr.length - 1; while (left < right) { int sum = arr[first] + arr[second] + arr[left] + arr[right]; if (sum == targetSum) { // Found the quadruplet List<Integer> quadruplet = new ArrayList<>(); quadruplet.add(arr[first]); quadruplet.add(arr[second]); quadruplet.add(arr[left]); quadruplet.add(arr[right]); quadruplets.add(quadruplet); left++; right--; // Skip same element to avoid duplicate quadruplets while (left < right && arr[left] == arr[left - 1]) { left++; } // Skip same element to avoid duplicate quadruplets while (left < right && arr[right] == arr[right + 1]) { right--; } } // We need a pair with a bigger sum else if (sum < targetSum) { left++; } // We need a pair with a smaller sum else { right--; } }} public static void printQuad(List<Integer> vec, int target) { int[] array = new int[vec.size()]; for(int i = 0; i < vec.size(); i++) array[i] = vec.get(i); List<List<Integer>> result = searchQuadruplets(array, target); for (int j = 0; j < result.size(); j++) { List<Integer> quadruplet = result.get(j); if (j == 0) { System.out.print("["); } System.out.print("["); for (int i = 0; i < quadruplet.size(); i++) { System.out.print(quadruplet.get(i)); if (i != quadruplet.size() - 1) { System.out.print(", "); } else { System.out.print("]"); } } if (j != result.size() - 1) { System.out.print(", "); } else { System.out.print("]"); } } } public static void main(String[] args) { List<Integer> vec = Arrays.asList(4, 1, 2, -1, 1, -3); int target = 1; printQuad(vec, target); }} |
C#
// C# program to find four elements that sum to a given// valueusing System;using System.Collections.Generic;public class GFG { // Function to find quadruplets public static List<List<int> > SearchQuadruplets(int[] arr, int target) { Array.Sort(arr); List<List<int> > quadruplets = new List<List<int> >(); for (int i = 0; i < arr.Length - 3; i++) { if (i > 0 && arr[i] == arr[i - 1]) { // Skip same element to avoid duplicate continue; } for (int j = i + 1; j < arr.Length - 2; j++) { if (j > i + 1 && arr[j] == arr[j - 1]) { // Skip same element to avoid duplicate // quad continue; } SearchPairs(arr, target, i, j, quadruplets); } } return quadruplets; } // Function to search Quadruplets private static void SearchPairs(int[] arr, int targetSum, int first, int second, List<List<int> > quadruplets) { int left = second + 1; int right = arr.Length - 1; while (left < right) { int sum = arr[first] + arr[second] + arr[left] + arr[right]; if (sum == targetSum) { // Found the quadruplet List<int> quadruplet = new List<int>(); quadruplet.Add(arr[first]); quadruplet.Add(arr[second]); quadruplet.Add(arr[left]); quadruplet.Add(arr[right]); quadruplets.Add(quadruplet); left++; right--; // Skip same element to avoid duplicate // quadruplets while (left < right && arr[left] == arr[left - 1]) { left++; } // Skip same element to avoid duplicate // quadruplets while (left < right && arr[right] == arr[right + 1]) { right--; } } // We need a pair with a bigger sum else if (sum < targetSum) { left++; } // We need a pair with a smaller sum else { right--; } } } public static void PrintQuad(List<int> vec, int target) { List<List<int> > result = SearchQuadruplets(vec.ToArray(), target); Console.Write("["); for (int j = 0; j < result.Count; j++) { List<int> quadruplet = result[j]; Console.Write("["); for (int i = 0; i < quadruplet.Count; i++) { Console.Write(quadruplet[i]); if (i != quadruplet.Count - 1) { Console.Write(", "); } else { Console.Write("]"); } } if (j != result.Count - 1) { Console.Write(", "); } else { Console.Write("]"); } } } static public void Main() { // Code List<int> vec = new List<int>(); vec.Add(4); vec.Add(1); vec.Add(2); vec.Add(-1); vec.Add(1); vec.Add(-3); int target = 1; PrintQuad(vec, target); }}// This code is contributed by karthik |
Javascript
<script>// JavaScript program to find four elements that sum to a given// value// Function to find quadrupletsconst searchQuadruplets = (arr, target) => { arr.sort((a, b) => a - b); let quadruplets = []; for (let i = 0; i < arr.length - 3; i++) { // Skip same element to avoid duplicate if (i > 0 && arr[i] === arr[i - 1]) { continue; } for (let j = i + 1; j < arr.length - 2; j++) { if (j > i + 1 && arr[j] === arr[j - 1]) { // Skip same element to avoid duplicate quad continue; } searchPairs(arr, target, i, j, quadruplets); } } return quadruplets;};// Function to search Quadrupletsconst searchPairs = (arr, targetSum, first, second, quadruplets) => { let left = second + 1; let right = arr.length - 1; while (left < right) { let sum = arr[first] + arr[second] + arr[left] + arr[right]; if (sum === targetSum) { let quadruplet = [arr[first], arr[second], arr[left], arr[right]]; quadruplets.push(quadruplet); left++; right--; // Skip same element to avoid duplicate quadruplets while (left < right && arr[left] === arr[left - 1]) { left++; } // Skip same element to avoid duplicate quadruplets while (left < right && arr[right] === arr[right + 1]) { right--; } } // We need a pair with a bigger sum else if (sum < targetSum) { left++; } // We need a pair with a smaller sum else { right--; } }};const printQuad = (vec, target) => { let array = Array.from(vec); let result = searchQuadruplets(array, target); document.write("["); for (let j = 0; j < result.length; j++) { let quadruplet = result[j]; document.write("["); for (let i = 0; i < quadruplet.length; i++) { document.write(quadruplet[i]); if (i !== quadruplet.length - 1) { document.write(", "); } else { document.write("]"); } } if (j !== result.length - 1) { document.write(", "); } else { document.write("]"); } }};let vec = [4, 1, 2, -1, 1, -3];let target = 1;printQuad(vec, target);// This code is contributed by lokesh.</script> |
Python3
# Python program to find four elements that sum to a given# value# Function to search Quadrupletsdef SearchPairs(arr, targetSum, first, second, quadruplets): left = second + 1 right = len(arr) - 1 while left < right: sum = arr[first] + arr[second] + arr[left] + arr[right] if sum == targetSum: # Found the quadruplet quadruplet = [] quadruplet.append(arr[first]) quadruplet.append(arr[second]) quadruplet.append(arr[left]) quadruplet.append(arr[right]) quadruplets.append(quadruplet) left += 1 right -= 1 # Skip same element to avoid duplicate quadruplets while left < right and arr[left] == arr[left - 1]: left += 1 # Skip same element to avoid duplicate quadruplets while left < right and arr[right] == arr[right + 1]: right -= 1 # We need a pair with a bigger sum elif sum < targetSum: left += 1 # We need a pair with a smaller sum else: right -= 1# Function to find quadrupletsdef SearchQuadruplets(arr, target): arr.sort() quadruplets = [] for i in range(len(arr) - 3): if i > 0 and arr[i] == arr[i - 1]: # Skip same element to avoid duplicate continue for j in range(i + 1, len(arr) - 2): if j > i + 1 and arr[j] == arr[j - 1]: # Skip same element to avoid duplicate quad continue SearchPairs(arr, target, i, j, quadruplets) return quadrupletsdef PrintQuad(vec, target): result = SearchQuadruplets(vec, target) print("[", end="") for j in range(len(result)): quadruplet = result[j] print("[", end="") for i in range(len(quadruplet)): print(quadruplet[i], end="") if i != len(quadruplet) - 1: print(", ", end="") else: print("]", end="") if j != len(result) - 1: print(", ", end="") else: print("]", end="")def main(): # Code vec = [4, 1, 2, -1, 1, -3] target = 1 PrintQuad(vec, target)if __name__ == "__main__": main()# This code is contributed by shivamsharma215 |
Output:
[[-3, -1, 1, 4], [-3, 1, 1, 2]]
Time complexity: Sorting the array will take O(N*logN). Overall searchQuadruplets() will take O(N * logN + N^3), which is asymptotically equivalent to O(N^3). Auxiliary Space complexity: The auxiliary space complexity of the above algorithm will be O(N) which is required for sorting. Similar Articles:
- Find four elements that sum to a given value | Set 1 (n^3 solution)
- Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution)
- Find four elements that sum to a given value | Set 3 (Hashmap)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
