Find four elements that sum to a given value | Two-Pointer approach

0 0 8 minutes read

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 code
int 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 quadruplets
public 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 Quadruplets
private 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
// value
 
using 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 quadruplets
const 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 Quadruplets
const 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 Quadruplets
def 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 quadruplets
def 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 quadruplets
 
 
def 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:

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 zambiatek!