Given an array arr[] consisting of N integers and an integer K, the task is to print all possible unique quadruplets (arr[i], arr[j], arr[k], arr[l]) whose sum is K such that all their indices are distinct.
Examples:
Input: arr[] = {1, 0, -1, 0, -2, 2}, K = 0
Output:
-2 -1 1 2
-2 0 0 2
-1 0 0 1
Explanation:
Below are the quadruplets whose sum is K (= 0):
- {-2, -1, 1, 2}
- {-2, 0, 0, 2}
- {-1, 0, 0, 1}
Input: arr[] = {1, 2, 3, -1}, target = 5
Output:
1 2 3 -1
Naive Approach: The simplest approach is to generate all possible quadruplets from the given array arr[] and if the sum of elements of the quadruplets is K, then insert the current quadruplets in the HashSet to avoid the count of duplicates quadruplets. After checking for all the quadruplets, print all the quadruplets stored in the HashSet.
Time Complexity: O(N4)
Auxiliary Space: O(N4)
Efficient Approach: The above approach can also be optimized by using the idea of generating all possible pairs of the given array. Follow the given steps to solve the problem:
- Initialize a HashMap, say ans that stores all the possible quadruplets.
- Initialize a HashMap, say M that stores the sum of all possible pairs of the given array with their corresponding indices.
- Generate all possible pairs of the given array and store the sum of all pairs of elements (arr[i], arr[j]) with their indices (i, j) in the HashMap M.
- Now, generate all possible pairs of the given array again and for each sum of all pairs of elements (arr[i], arr[j]) if the value (K – sum) exists in the HashMap M, then store the current quadruplets in the HashMap ans.
- After completing the above steps, print all the quadruplets stored in the HashMap ans.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Stores the pair of indicesclass Pair { public: int index1, index2; Pair(int x, int y) { index1 = x; index2 = y; }};// Function to find the all the// unique quadruplets with the// elements at different indicesvoid GetQuadruplets(vector<int>& nums, int target){ // Stores the sum mapped to // a List Of Pair<i, j> map<int, vector<Pair> > map; // Generate all possible pairs // for the HashMap for (int i = 0; i < nums.size() - 1; i++) { for (int j = i + 1; j < nums.size(); j++) { // Find the sum of pairs // of elements int sum = nums[i] + nums[j]; // If the sum doesn't // exists then update // with the new pairs if (map.find(sum) == map.end()) { vector<Pair> temp; Pair p(i, j); temp.push_back(p); // Update the hashmap map[sum] = temp; } // Otherwise, push the new // pair of indices to the // current sum else { vector<Pair> temp = map[sum]; Pair p(i, j); temp.push_back(p); // Update the hashmap map[sum] = temp; } } } // Stores all the Quadruplets set<string> ans; for (int i = 0; i < nums.size() - 1; i++) { for (int j = i + 1; j < nums.size(); j++) { int lookUp = target - (nums[i] + nums[j]); // If the sum with value (K - sum) exists if (map.find(lookUp) != map.end()) { // Get the pair of // indices of sum vector<Pair> temp = map[lookUp]; for (Pair pair : temp) { // Check if i, j, k and l are distinct // or not if (pair.index1 != i && pair.index1 != j && pair.index2 != i && pair.index2 != j) { vector<int> l1 = { nums[pair.index1], nums[pair.index2], nums[i], nums[j] }; // Sort the list to avoid duplicacy sort(l1.begin(), l1.end()); // Update the hashset ans.insert(to_string(l1[0]) + " " + to_string(l1[1]) + " " + to_string(l1[2]) + " " + to_string(l1[3])); } } } } } // Print all the Quadruplets for (string arr : ans) { cout << arr << endl; }}// Driver Codeint main(){ vector<int> arr = { 1, 0, -1, 0, -2, 2 }; int K = 0; GetQuadruplets(arr, K);}// This code is contributed by phasing17. |
Java
// Java program for the above approachimport java.io.*;import java.util.*;public class GFG { // Stores the pair of indices static class Pair { int index1; int index2; // Constructor Pair(int x, int y) { index1 = x; index2 = y; } } // Function to find the all the // unique quadruplets with the // elements at different indices public static void GetQuadruplets(ArrayList<Integer> nums, int target) { // Stores the sum mapped to // a List Of Pair<i, j> HashMap<Integer, ArrayList<Pair> > map = new HashMap<>(); // Generate all possible pairs // for the HashMap for (int i = 0; i < nums.size() - 1; i++) { for (int j = i + 1; j < nums.size(); j++) { // Find the sum of pairs // of elements int sum = nums.get(i) + nums.get(j); // If the sum doesn't // exists then update // with the new pairs if (!map.containsKey(sum)) { ArrayList<Pair> temp = new ArrayList<>(); Pair p = new Pair(i, j); temp.add(p); // Update the hashmap map.put(sum, temp); } // Otherwise, push the new // pair of indices to the // current sum else { ArrayList<Pair> temp = map.get(sum); Pair p = new Pair(i, j); temp.add(p); // Update the hashmap map.put(sum, temp); } } } // Stores all the Quadruplets HashSet<ArrayList<Integer> > ans = new HashSet<ArrayList<Integer> >(); for (int i = 0; i < nums.size() - 1; i++) { for (int j = i + 1; j < nums.size(); j++) { int lookUp = target - (nums.get(i) + nums.get(j)); // If the sum with value // (K - sum) exists if (map.containsKey(lookUp)) { // Get the pair of // indices of sum ArrayList<Pair> temp = map.get(lookUp); for (Pair pair : temp) { // Check if i, j, k // and l are distinct // or not if (pair.index1 != i && pair.index1 != j && pair.index2 != i && pair.index2 != j) { ArrayList<Integer> values = new ArrayList<>(); values.add( nums.get(pair.index1)); values.add( nums.get(pair.index2)); values.add(nums.get(i)); values.add(nums.get(j)); // Sort the list to // avoid duplicacy Collections.sort(values); // Update the hashset ans.add(values); } } } } } // Print all the Quadruplets for (ArrayList<Integer> arr : ans) { System.out.println(arr); } } // Driver Code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(); arr.add(1); arr.add(0); arr.add(-1); arr.add(0); arr.add(-2); arr.add(2); int K = 0; GetQuadruplets(arr, K); }} |
Python3
# Store the pair of indicesclass Pair: def __init__(self, x, y): self.index1 = x self.index2 = y# Function to find the all the unique quadruplets# with the elements at different indicesdef GetQuadruplets(nums, target): # Store the sum mapped to a list of pair indices map = {} # Generate all possible pairs for the map for i in range(len(nums) - 1): for j in range(i + 1, len(nums)): # Find the sum of pairs of elements sum = nums[i] + nums[j] # If the sum doesn't exist then update with the new pairs if sum not in map: map[sum] = [Pair(i, j)] # Otherwise, add the new pair of indices to the current sum else: map[sum].append(Pair(i, j)) # Store all the Quadruplets ans = set() for i in range(len(nums) - 1): for j in range(i + 1, len(nums)): lookUp = target - (nums[i] + nums[j]) # If the sum with value (K - sum) exists if lookUp in map: # Get the pair of indices of sum temp = map[lookUp] for pair in temp: # Check if i, j, k and l are distinct or not if pair.index1 != i and pair.index1 != j and pair.index2 != i and pair.index2 != j: l1 = [nums[pair.index1], nums[pair.index2], nums[i], nums[j]] # Sort the list to avoid duplicacy l1.sort() # Update the set ans.add(tuple(l1)) # Print all the Quadruplets print(*reversed(list(ans)), sep = '\n')# Driver Codearr = [1, 0, -1, 0, -2, 2]K = 0GetQuadruplets(arr, K)# This code is contributed by phasing17. |
C#
using System;using System.Collections.Generic;using System.Linq;class GFG{ // Stores the pair of indices class Pair { public int index1; public int index2; // Constructor public Pair(int x, int y) { index1 = x; index2 = y; } } // Function to find the all the // unique quadruplets with the // elements at different indices public static void GetQuadruplets(List<int> nums, int target) { // Stores the sum mapped to // a List Of Pair<i, j> Dictionary<int, List<Pair>> map = new Dictionary<int, List<Pair>>(); // Generate all possible pairs // for the HashMap for (int i = 0; i < nums.Count - 1; i++) { for (int j = i + 1; j < nums.Count; j++) { // Find the sum of pairs // of elements int sum = nums[i] + nums[j]; // If the sum doesn't // exists then update // with the new pairs if (!map.ContainsKey(sum)) { List<Pair> temp = new List<Pair>(); Pair p = new Pair(i, j); temp.Add(p); // Update the hashmap map.Add(sum, temp); } // Otherwise, push the new // pair of indices to the // current sum else { List<Pair> temp = map[sum]; Pair p = new Pair(i, j); temp.Add(p); // Update the hashmap map[sum] = temp; } } } // Stores all the Quadruplets HashSet<Tuple<int, int, int, int>> ans = new HashSet<Tuple<int, int, int, int>>(); for (int i = 0; i < nums.Count - 1; i++) { for (int j = i + 1; j < nums.Count; j++) { int lookUp = target - (nums[i] + nums[j]); // If the sum with value (K - sum) exists if (map.ContainsKey(lookUp)) { // Get the pair of // indices of sum List<Pair> temp = map[lookUp]; foreach (Pair pair in temp) { // Check if i, j, k and l are distinct // or not if (pair.index1 != i && pair.index1 != j && pair.index2 != i && pair.index2 != j) { List<int> l1 = new List<int> {nums[pair.index1], nums[pair.index2], nums[i], nums[j]}; // Sort the list to avoid duplicacy l1.Sort(); Tuple<int, int, int, int> values = Tuple.Create(l1[0], l1[1], l1[2], l1[3]); // Update the hashset ans.Add(values); } } } } } // Print all the Quadruplets foreach (var arr in ans) { Console.WriteLine(String.Join(", ", arr)); } } // Driver Code public static void Main(string[] args) { List<int> arr = new List<int>(); arr.Add(1); arr.Add(0); arr.Add(-1); arr.Add(0); arr.Add(-2); arr.Add(2); int K = 0; GetQuadruplets(arr, K); }}// This code is contributed by phasing17. |
Javascript
// Stores the pair of indicesclass Pair { constructor(x, y) { this.index1 = x; this.index2 = y; }}// Function to find the all the// unique quadruplets with the// elements at different indicesfunction GetQuadruplets(nums, target) { // Stores the sum mapped to // a List Of Pair<i, j> let map = new Map(); // Generate all possible pairs // for the HashMap for (let i = 0; i < nums.length - 1; i++) { for (let j = i + 1; j < nums.length; j++) { // Find the sum of pairs // of elements let sum = nums[i] + nums[j]; // If the sum doesn't // exists then update // with the new pairs if (!map.has(sum)) { let temp = []; let p = new Pair(i, j); temp.push(p); // Update the hashmap map.set(sum, temp); } // Otherwise, push the new // pair of indices to the // current sum else { let temp = map.get(sum); let p = new Pair(i, j); temp.push(p); // Update the hashmap map.set(sum, temp); } } } // Stores all the Quadruplets let ans = new Set(); for (let i = 0; i < nums.length - 1; i++) { for (let j = i + 1; j < nums.length; j++) { let lookUp = target - (nums[i] + nums[j]); // If the sum with value (K - sum) exists if (map.has(lookUp)) { // Get the pair of // indices of sum let temp = map.get(lookUp); for (let pair of temp) { // Check if i, j, k and l are distinct // or not if (pair.index1 !== i && pair.index1 !== j && pair.index2 !== i && pair.index2 !== j) { let l1 = [nums[pair.index1], nums[pair.index2], nums[i], nums[j]]; // Sort the list to avoid duplicacy l1.sort(function(a, b) { return a - b; }); // Update the hashset ans.add(l1.join(" ")); } } } } } // Print all the Quadruplets for (let arr of ans) { console.log(arr); }}// Driver Codelet arr = [1, 0, -1, 0, -2, 2];let K = 0;GetQuadruplets(arr, K);// This code is contributed by phasing17. |
Output:
[-2, 0, 0, 2] [-1, 0, 0, 1] [-2, -1, 1, 2]
Time Complexity: O(N2 * log N)
Auxiliary Space: O(N2)
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!
