Open In App

4 Sum - Find any quadruplet having given sum

Last Updated : 07 Oct, 2024
Comments
Improve
Suggest changes
Like Article
Like
Report

Given an array arr[] of n integers and an integer target, the task is to find any quadruplet in arr[] such that it's sum is equal to the target.

Note: If there are multiple quadruplets with sum = target, return any one of them.

Examples:

Input: arr[] = {2, 4, 6, 8, 1, 3}, target = 15
Output: {2, 4, 6, 3}
Explanation: The quadruplet {2, 4, 6, 3} has sum = 15.

Input: arr[] = {1, 2, 3, 4, 10}, target = 20
Output: {}
Explanation: No quadruplet adds up to a sum of 20.

Table of Content

[Naive Approach] - Explore all the subsets of size four - O(n^4) Time and O(1) Space

The idea is to generate all possible quadruplets using four nested loops and calculate the sum of each quadruplet. If the sum of a quadruplet is equal to target, return that quadruplet.

C++ 
// C++ program to find a quadruplet with sum
// equal to target by exploring all quadruplets

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

vector<int> findQuadruplet(vector<int>& arr, int target) {
    int n = arr.size();
    
    // Generating all possible quadruplets
    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++) {
                    int currSum = arr[i] + arr[j] + arr[k] + arr[l];
                    
                    // If current sum equals target, we have found desired quadruplet
                    if (currSum == target) {
                        return {arr[i], arr[j], arr[k], arr[l]};
                    }
                }
            }
        }
    }
  
    // Return empty vector if no quadruplet found
    return {};
}

int main() {
    vector<int> arr = {2, 4, 6, 8, 1, 3}; 
    int target = 15; 
    
    vector<int> res = findQuadruplet(arr, target);
    for (int i = 0; i < res.size(); i++)
      	cout << res[i] << " ";
  
    return 0;
}
C 
// C program to find a quadruplet with sum
// equal to target by exploring all quadruplets

#include <stdio.h>

int* findQuadruplet(int* arr, int n, int target) {
  
    // Generating all possible quadruplets
    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++) {
                    int currSum = arr[i] + arr[j] + arr[k] + arr[l];
                    
                    // If current sum equals target, we have found desired quadruplet
                    if (currSum == target) {
                        int* res = (int*)malloc(4 * sizeof(int));
                        res[0] = arr[i];
                        res[1] = arr[j];
                        res[2] = arr[k];
                        res[3] = arr[l];
                        return res;
                    }
                }
            }
        }
    }
  
    // Return NULL if no quadruplet found
    return NULL;
}

int main() {
    int arr[] = {2, 4, 6, 8, 1, 3}; 
    int target = 15; 
    int n = sizeof(arr) / sizeof(arr[0]);
    
    int* res = findQuadruplet(arr, n, target);
    if (res != NULL) {
        for (int i = 0; i < 4; i++)
            printf("%d ", res[i]);
    }
  
    return 0;
}
Java 
// Java program to find a quadruple with sum
// equal to target by exploring all quadruplets

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

class GfG {
    
    static List<Integer> findQuadruplet(int[] arr, int target) {
        int n = arr.length;

        // Generating all possible quadruplets
        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++) {
                        int currSum = arr[i] + arr[j] + arr[k] + arr[l];

                        // If current sum equals target, we have found desired quadruplet
                        if (currSum == target) {
                            List<Integer> result = new ArrayList<>();
                            result.add(arr[i]);
                            result.add(arr[j]);
                            result.add(arr[k]);
                            result.add(arr[l]);
                            return result;
                        }
                    }
                }
            }
        }

        // Return empty list if no quadruplet found
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 1, 3}; 
        int target = 15; 
        
        List<Integer> res = findQuadruplet(arr, target);
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i) + " ");
        }
    }
}
Python 
# Python program to find a quadruple with sum
# equal to target by exploring all quadruplets

def findQuadruplet(arr, target):
    n = len(arr)
    
    # Generating all possible quadruplets
    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):
                    currSum = arr[i] + arr[j] + arr[k] + arr[l]
                    
                    # If current sum equals target, we have found desired quadruplet
                    if currSum == target:
                        return [arr[i], arr[j], arr[k], arr[l]]
    
    # Return empty list if no quadruplet found
    return []

if __name__ == "__main__":
    arr = [2, 4, 6, 8, 1, 3] 
    target = 15 
    
    res = findQuadruplet(arr, target)
    for i in range(len(res)):
        print(res[i], end=" ")
C# 
// C# program to find a quadruple with sum
// equal to target by exploring all quadruplets

using System;
using System.Collections.Generic;

class GfG {
    static List<int> findQuadruplet(List<int> arr, int target) {
        int n = arr.Count;

        // Generating all possible quadruplets
        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++) {
                        int currSum = arr[i] + arr[j] + arr[k] + arr[l];

                        // If current sum equals target, we have found desired quadruplet
                        if (currSum == target) {
                            return new List<int> { arr[i], arr[j], arr[k], arr[l] };
                        }
                    }
                }
            }
        }

        // Return empty list if no quadruplet found
        return new List<int>();
    }

    static void Main() {
        List<int> arr = new List<int> { 2, 4, 6, 8, 1, 3 };
        int target = 15;

        List<int> res = findQuadruplet(arr, target);
        for (int i = 0; i < res.Count; i++)
            Console.Write(res[i] + " ");
    }
}
JavaScript 
// JavaScript program to find a quadruplet with sum
// equal to target by exploring all quadruplets

function findQuadruplet(arr, target) {
    const n = arr.length;
    
    // Generating all possible quadruplets
    for (let i = 0; i < n - 3; i++) {
        for (let j = i + 1; j < n - 2; j++) {
            for (let k = j + 1; k < n - 1; k++) {
                for (let l = k + 1; l < n; l++) {
                    const currSum = arr[i] + arr[j] + arr[k] + arr[l];
                    
                    // If current sum equals target, we have found desired quadruplet
                    if (currSum === target) {
                        return [arr[i], arr[j], arr[k], arr[l]];
                    }
                }
            }
        }
    }
  
    // Return empty array if no quadruplet found
    return [];
}

const arr = [2, 4, 6, 8, 1, 3]; 
const target = 15; 

const res = findQuadruplet(arr, target);
console.log(res.join(" "));

Output
2 4 6 3

[Expected Approach] Sorting and Two Pointers Technique – O(n^3) time and O(1) space

Initially, we sort the input array so that we can apply two pointers technique. Then, we fix the first two elements of the quadruplet using two nested loops and inside the second nested loop we use two pointers technique to find the remaining two elements. Set one pointer at the beginning (left) and another at the end (right) of the remaining array. We then check the sum of all these four elements and compare it with the given target:

  • If sum < target, move left pointer towards right to increase the sum.
  • If sum > target, move right pointer towards left to decrease the sum.
  • If sum == target, we’ve found the quadruple.
C++ 
// C++ program to find a quadruplet having 
// sum target using two pointers technique

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

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

    // Sorting the array to use two pointers technique
    sort(arr.begin(), arr.end());
  
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            int l = j + 1, r = n - 1;

            while (l < r) {
                int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                // If currSum is equal to target,
              	// we have found the desired quadruplet
                if (currSum == target) {
                    return {arr[i], arr[j], arr[l], arr[r]};
                }

                // If currSum exceeds the target, move
				// the right pointer left to reduce the sum
                if (currSum > target)
                    r--;

                // If currSum is less than target, move 
				// the left pointer right to increase the sum
                else
                    l++;
            }
        }
    }
	
  	// Return empty array if no quadruplet found
    return {};
}

int main() {
    vector<int> arr = {2, 4, 6, 8, 1, 3};
    int target = 15;

    vector<int> res = findQuadruplet(arr, target);
 	for (int i = 0; i < res.size(); i++) 
      		cout << res[i] << " ";
          
    return 0;
}
C 
// C program to find a quadruplet having 
// sum target using two pointer technique

#include <stdio.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* findQuadruplet(int* arr, int n, int target) {
    
    // Sorting the array to use two pointers technique
    qsort(arr, n, sizeof(int), compare);

    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            int l = j + 1, r = n - 1;

            while (l < r) {
                int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                // If currSum is equal to target,
                // we have found the desired quadruplet
                if (currSum == target) {
                    int* result = (int*)malloc(4 * sizeof(int));
                    result[0] = arr[i];
                    result[1] = arr[j];
                    result[2] = arr[l];
                    result[3] = arr[r];
                    return result;
                }

                // If currSum exceeds the target, move
                // the right pointer left to reduce the sum
                if (currSum > target)
                    r--;

                // If currSum is less than target, move 
                // the left pointer right to increase the sum
                else
                    l++;
            }
        }
    }

    // Return NULL if no quadruplet found
    return NULL;
}

int main() {
    int arr[] = {2, 4, 6, 8, 1, 3};
    int target = 15;
    int n = sizeof(arr) / sizeof(arr[0]);

    int* res = findQuadruplet(arr, n, target);
    if (res != NULL) {
        for (int i = 0; i < 4; i++)
            printf("%d ", res[i]);
    } 
    return 0;
}
Java 
// Java program to find a quadruplet having 
// sum target using two pointer technique

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

class GfG {
    
    static List<Integer> findQuadruplet(int[] arr, int target) {
        int n = arr.length;

        // Sorting the array to use two pointers technique
        Arrays.sort(arr);
  
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                int l = j + 1, r = n - 1;

                while (l < r) {
                    int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                    // If currSum is equal to target,
                    // we have found the desired quadruplet
                    if (currSum == target)
                        return Arrays.asList(arr[i], arr[j], arr[l], arr[r]);

                    // If currSum exceeds the target, move
                    // the right pointer left to reduce the sum
                    if (currSum > target)
                        r--;

                    // If currSum is less than target, move 
                    // the left pointer right to increase the sum
                    else
                        l++;
                }
            }
        }
    
        // Return empty array if no quadruplet found
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 1, 3};
        int target = 15;

        List<Integer> res = findQuadruplet(arr, target);
        for (int i = 0; i < res.size(); i++) 
            System.out.print(res.get(i) + " ");
    }
}
Python 
# Python program to find a quadruplet having 
# sum target using two pointers technique

def findQuadruplet(arr, target):
    n = len(arr)

    # Sorting the array to use two pointers technique
    arr.sort()
  
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            l, r = j + 1, n - 1

            while l < r:
                currSum = arr[i] + arr[j] + arr[l] + arr[r]

                # If currSum is equal to target,
                # we have found the desired quadruplet
                if currSum == target:
                    return [arr[i], arr[j], arr[l], arr[r]]

                # If currSum exceeds the target, move
                # the right pointer left to reduce the sum
                if currSum > target:
                    r -= 1

                # If currSum is less than target, move 
                # the left pointer right to increase the sum
                else:
                    l += 1
    
    # Return empty array if no quadruplet found
    return []

if __name__ == "__main__":
    arr = [2, 4, 6, 8, 1, 3]
    target = 15

    res = findQuadruplet(arr, target)
    for i in range(len(res)):
        print(res[i], end=" ")
C# 
// C# program to find a quadruplet having 
// sum target using two pointer technique

using System;
using System.Collections.Generic;

class GfG {
    static List<int> findQuadruplet(List<int> arr, int target) {
        int n = arr.Count;

        // Sorting the array to use two pointers technique
        arr.Sort();
  
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                int l = j + 1, r = n - 1;

                while (l < r) {
                    int currSum = arr[i] + arr[j] + arr[l] + arr[r];

                    // If currSum is equal to target,
                    // we have found the desired quadruplet
                    if (currSum == target) {
                        return new List<int> { arr[i], arr[j], arr[l], arr[r] };
                    }

                    // If currSum exceeds the target, move
                    // the right pointer left to reduce the sum
                    if (currSum > target)
                        r--;

                    // If currSum is less than target, move 
                    // the left pointer right to increase the sum
                    else
                        l++;
                }
            }
        }
	
        // Return empty array if no quadruplet found
        return new List<int>();
    }

    static void Main() {
        List<int> arr = new List<int> { 2, 4, 6, 8, 1, 3 };
        int target = 15;

        List<int> res = findQuadruplet(arr, target);
        for (int i = 0; i < res.Count; i++)
            Console.Write(res[i] + " ");
    }
}
JavaScript 
// JavaScript program to find a quadruplet having 
// sum target using two pointer technique

function findQuadruplet(arr, target) {
    let n = arr.length;

    // Sorting the array to use two pointers technique
    arr.sort((a, b) => a - b);
  
    for (let i = 0; i < n - 3; i++) {
        for (let j = i + 1; j < n - 2; j++) {
            let l = j + 1, r = n - 1;

            while (l < r) {
                let currSum = arr[i] + arr[j] + arr[l] + arr[r];

                // If currSum is equal to target,
                // we have found the desired quadruplet
                if (currSum === target) {
                    return [arr[i], arr[j], arr[l], arr[r]];
                }

                // If currSum exceeds the target, move
                // the right pointer left to reduce the sum
                if (currSum > target) {
                    r--;
                }

                // If currSum is less than target, move 
                // the left pointer right to increase the sum
                else {
                    l++;
                }
            }
        }
    }
	
    // Return empty array if no quadruplet found
    return [];
}

const arr = [2, 4, 6, 8, 1, 3];
const target = 15;

const res = findQuadruplet(arr, target);
console.log(res.join(" "));

Output
1 2 4 8

Next Article
Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, ...

A
amitja57a
Improve
Article Tags :
Practice Tags :

Similar Reads

We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox
  翻译：