Data Modelling & AI Data Structure & Algorithm

Find all distinct quadruplets in an array that sum up to a given value

23 June 2025

0

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(N⁴)
Auxiliary Space: O(N⁴)

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 indices
class 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 indices
void 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 Code
int 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 approach
 
import 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 indices
class 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 indices
def 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 Code
arr = [1, 0, -1, 0, -2, 2]
K = 0
GetQuadruplets(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 indices
class Pair {
  constructor(x, y) {
    this.index1 = x;
    this.index2 = y;
  }
}
 
// Function to find the all the
// unique quadruplets with the
// elements at different indices
function 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 Code
let 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(N² * log N)
Auxiliary Space: O(N²)

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!

Find all distinct quadruplets in an array that sum up to a given value

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Nano Banana’s viral features are coming to more Google apps

Google defends Android’s controversial sideloading policy

Nothing’s new AI Tools let you build apps with just a prompt

Apple iPhone 17 Pro Max review: As subtle as a sledgehammer, and just as powerful

EDITOR PICKS

Nano Banana’s viral features are coming to more Google apps

Google defends Android’s controversial sideloading policy

Nothing’s new AI Tools let you build apps with just a prompt

POPULAR POSTS

Nano Banana’s viral features are coming to more Google apps

Google defends Android’s controversial sideloading policy

Nothing’s new AI Tools let you build apps with just a prompt

POPULAR CATEGORY

ABOUT US

FOLLOW US