4 Sum - Find all Quadruplets with Given Sum

Last Updated : 20 Oct, 2024

Given an array arr[] and a target value, the task is to find all possible indexes (i, j, k, l) of quadruplets (arr[i], arr[j], arr[k], arr[l]) whose sum is given target and all indexes in a quadruple are distinct (i != j, j != k, and k != l). We need to return indexes of a quadruple in sorted order, i.e., i < j < k < l.

Examples:

Input: arr[] = {1, 5, 3, 1, 2, 10}, target = 20
Output: [1, 2, 4, 5]
Explanation: Only quadruplet satisfying the conditions is arr[1] + arr[2] + arr[4] + arr[5] = 5 + 3 + 2 + 10 = 20.
Input: arr[] = {4, 5, 3, 1, 2, 4}, target = 13
Output: [[0, 1, 2, 5], [0, 1, 2, 3], [1, 2, 3, 5]]
Explanation: Three quadruplets with sum 13 are:
arr[0] + arr[2] + arr[4] + arr[5] = 4 + 3 + 2 + 4 = 13
arr[0] + arr[1] + arr[2] + arr[3] = 4 + 5 + 3 + 1 = 13
arr[1] + arr[2] + arr[3] + arr[5] = 5 + 3 + 1 + 4 = 13
Input: arr[] = {1, 1, 1, 1, 1}, target = 4
Output: [[1, 1, 2, 3], [0, 1, 2, 4], [0, 1, 3, 4], [0, 2, 3, 4], [1, 2, 3, 4]]
Explanation:
arr[0] + arr[1] + arr[2] + arr[3] = 4
arr[0] + arr[1] + arr[2] + arr[4] = 4
arr[0] + arr[1] + arr[3] + arr[4] = 4
arr[0] + arr[2] + arr[3] + arr[4] = 4
arr[1] + arr[2] + arr[3] + arr[4] = 4

Naive Approach - O(n^4) Time and O(1) Space

The simplest approach is to generate all possible quadruplets from the given array arr[] and if the sum of elements of the quadruplets is equal to target, then add it to the result.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> fourSum(vector<int>& arr, int target) {
    vector<vector<int>> res;
    int n = arr.size();

    // Four nested loops to generate all quadruples
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                for (int l = k + 1; l < n; l++) {
                  
                    // If the sum of the quadruple equals the 
                    // target, add it to the result
                    if (arr[i] + arr[j] + arr[k] + arr[l] == target) {
                        res.push_back({i, j, k, l});
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    vector<int> arr = {1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> ans = fourSum(arr, target);
    for (auto v : ans) {
        for (auto x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

public class FourSum {
    public static List<List<Integer>> fourSum(int[] arr, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = arr.length;

        // Four nested loops to generate all quadruples
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {

                        // If the sum of the quadruple equals the 
                        // target, add it to the result
                        if (arr[i] + arr[j] + arr[k] + arr[l] == target) {
                            res.add(List.of(i, j, k, l));
                        }
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> ans = fourSum(arr, target);
        for (List<Integer> v : ans) {
            for (int x : v) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
}

Python

def four_sum(arr, target):
    res = []
    n = len(arr)

    # Four nested loops to generate all quadruples
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            for k in range(j + 1, n - 1):
                for l in range(k + 1, n):
                    
                    # If the sum of the quadruple equals 
                    # the target, add it to the result
                    if arr[i] + arr[j] + arr[k] + arr[l] == target:
                        res.append([i, j, k, l])
    
    return res

# Driver Code
arr = [1, 0, -1, 0, -2, 2]
target = 0
ans = four_sum(arr, target)
for quad in ans:
    print(f"{quad[0]} {quad[1]} {quad[2]} {quad[3]}")

Efficient Approach - O(n^4) Time and O(n^2) Space

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 Hash Map, say mp that stores all possible pairs with a given pair sum Pairs sum is used as key and an array of pairs as value.
Generate all possible pairs and store their sums as keys and pairs themselves as values in mp.
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 (target - sum) exists in the Hash Map mp, then store the current quadruplets in the result set.
We use a set for result to avoid duplicates. Before we insert a quadruple in the result set, we sort it as per the question requirements.
Finally, we move all the result set quadruples in an array and return the array.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> fourSum(vector<int>& arr, int target) {
  
    int n = arr.size();
    unordered_map<int, vector<pair<int, int>>> mp;    

    // Ideally we should us an unordered_set here, but C++
    // does not support vector as a key in an unordered_set
    // So we have used set to keep the code simple. However
    // set internally uses Red Black Tree and has O(Log n)
    // time complexities for operations
    set<vector<int>> resset; 

    // Store all pairs for every possible pairs sum
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            mp[arr[i] + arr[j]].push_back({i, j});  
        }
    }

    // Pick the first two elements
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {          
            
            // Find pairs with the remaining sum
            int rem = target - arr[i] - arr[j];
            if (mp.find(rem) != mp.end()) {
                auto& pairs = mp[rem]; 

                for (auto& p : pairs) {
                  
                    // Ensure no two indexes are same in a quaduple and 
                    // all indexes are in sorted order
                    if (p.first != i && p.second != i && p.first != j && p.second != j) {
                        vector<int> curr = {p.first, p.second, i, j};
                        sort(curr.begin(), curr.end());
                        resset.insert(curr); 
                    }
                }
            }
        }
    }
    vector<vector<int>> res(resset.begin(), resset.end());
    return res;
}

// Driver Code
int main() {
    vector<int> arr = {1, 1, 1, 1, 1};  
    int target = 4;  
    vector<vector<int>> res = fourSum(arr, target);
    for (auto& quad : res) {
        for (int num : quad) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Java

import java.util.*;

public class FourSum {
    public static List<List<Integer>> fourSum(int[] arr, int target) {
        int n = arr.length;
        Map<Integer, List<int[]>> mp = new HashMap<>();    
        Set<List<Integer>> resset = new HashSet<>(); 

        // Store all pairs for every possible pairs sum
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                mp.computeIfAbsent(arr[i] + arr[j], k -> new ArrayList<>()).add(new int[]{i, j});
            }
        }

        // Pick the first two elements
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {          
              
                // Find pairs with the remaining sum
                int rem = target - arr[i] - arr[j];
                if (mp.containsKey(rem)) {
                    for (int[] p : mp.get(rem)) {
                      
                        // Ensure no two indexes are the same in a quadruple
                        // And all indexes are in sorted order
                        if (p[0] != i && p[1] != i && p[0] != j && p[1] != j) {
                            List<Integer> curr = Arrays.asList(p[0], p[1], i, j);
                            Collections.sort(curr);
                            resset.add(curr);
                        }
                    }
                }
            }
        }

        return new ArrayList<>(resset);
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 1};
        int target = 4;
        List<List<Integer>> res = fourSum(arr, target);
        for (List<Integer> quad : res) {
            quad.forEach(num -> System.out.print(num + " "));
            System.out.println();
        }
    }
}

Python

from collections import defaultdict

def four_sum(arr, target):
    n = len(arr)
    mp = defaultdict(list)
    resset = set()  # Set to avoid duplicates
    
    # Store all pairs for every possible pairs sum
    for i in range(n):
        for j in range(i + 1, n):
            mp[arr[i] + arr[j]].append((i, j))
    
    # Pick the first two elements
    for i in range(n - 1):
        for j in range(i + 1, n):
          
            # Find pairs with the remaining sum
            rem = target - arr[i] - arr[j]
            if rem in mp:
                for p in mp[rem]:
                  
                    # Ensure no two indexes are the same in a quadruple
                    # and all indexes are in sorted order
                    if p[0] != i and p[1] != i and p[0] != j and p[1] != j:
                        curr = tuple(sorted([p[0], p[1], i, j]))
                        resset.add(curr)

    return [list(quad) for quad in resset]

# Driver Code
arr = [1, 1, 1, 1, 1]
target = 4
res = four_sum(arr, target)
for quad in res:
    print(" ".join(map(str, quad)))

Java Program to Find a triplet that sum to a given value

dybydx

Improve

Article Tags :

Practice Tags :

4 Sum - Find all Quadruplets with Given Sum

Naive Approach - O(n^4) Time and O(1) Space

Efficient Approach - O(n^4) Time and O(n^2) Space

Similar Reads

Thank You!

What kind of Experience do you want to share?