4 Sum Problem

Given an array of integers arr and an integer target, find all unique quadruplets (four numbers) in the array that sum up to the given target value.

• A valid quadruplet is a set of four elements (a, b, c, d) such that a + b + c + d = target.
• All quadruplets must be unique. That means no two quadruplets can contain the same set of four numbers, even in a different order.
• The input array can contain duplicate numbers, but the result must contain only unique combinations.

If no such quadruplets exist, return an empty list.

Understanding the Problem

The "4 Sum" problem asks us to find all unique quadruplets (groups of four numbers) in a given array that add up to a specific target sum. The array can include positive numbers, negative numbers, and duplicates. For example, if the input is nums = [1, 0, -1, 0, -2, 2] and target = 0, we need to find all unique sets of four numbers whose sum equals 0.

Example

Let’s take nums = [1, 0, -1, 0, -2, 2] and target = 0.

After sorting the array, we get: [-2, -1, 0, 0, 1, 2]

We want to find combinations like [-2, -1, 1, 2] because -2 + -1 + 1 + 2 = 0.

Step-by-Step Approach

Instead of using brute force to try every combination of 4 numbers (which is very slow), we use a structured and efficient method:

Step 1: Sort the Array

Sorting helps us to:

• Quickly skip duplicate values
• Use the two-pointer technique for finding pairs

Step 2: Use Nested Loops to Fix First Two Numbers

We use two nested for loops to pick the first and second numbers of the quadruplet.

Step 3: Two-Pointer Technique for Remaining Two Numbers

Once the first two numbers are fixed, we use two pointers — left and right — to scan for the remaining two numbers that complete the quadruplet.

Step 4: Skip Duplicates

After each valid combination, we move the left and right pointers to skip over any duplicate values to avoid repeating the same quadruplets in the result.

Incorporating Edge Cases

Case 1: Empty Array or Less Than 4 Elements

If the array is empty or has fewer than 4 elements, we can’t form a quadruplet. Return an empty list: []

Case 2: All Elements Are the Same

Example: [2, 2, 2, 2, 2] with target = 8 → Only one valid quadruplet: [2, 2, 2, 2]. Skip remaining duplicates.

Case 3: No Valid Combination

If no group of 4 numbers adds up to the target, return an empty list.

Case 4: Negative and Positive Mix

The presence of both negative and positive numbers means valid quadruplets can be scattered across the array — sorting helps align them for scanning.

Why This Solution Works

By sorting and using nested loops with two pointers:

• We reduce time complexity to O(n³) — much faster than checking every O(n⁴) combination.
• We ensure that no duplicate sets are added to the result.
• We handle all edge cases with clear, logical checks.

Finally

This method is efficient, beginner-friendly, and scalable. It teaches good habits like sorting early, avoiding duplicate work, and breaking problems down step-by-step.

1. Given an array arr of size n and a target value target.
2. Sort the array in ascending order.
3. Fix the first element with index i (0 to n-4).
4. Fix the second element with index j (i+1 to n-3).
5. Use two pointers left = j+1 and right = n-1 to find two other numbers.
6. If the sum of the four elements equals target, store the quadruplet.
7. Move pointers intelligently while skipping duplicates to find all unique quadruplets.

#include <stdio.h>
#include <stdlib.h>

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

void fourSum(int* arr, int n, int target) {
    qsort(arr, n, sizeof(int), compare);

    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && arr[i] == arr[i-1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && arr[j] == arr[j-1]) continue;
            int left = j + 1, right = n - 1;
            while (left < right) {
                int total = arr[i] + arr[j] + arr[left] + arr[right];
                if (total == target) {
                    printf("%d %d %d %d\n", arr[i], arr[j], arr[left], arr[right]);
                    left++;
                    right--;
                    while (left < right && arr[left] == arr[left-1]) left++;
                    while (left < right && arr[right] == arr[right+1]) right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
}

int main() {
    int arr[] = {1, 0, -1, 0, -2, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 0;
    fourSum(arr, n, target);
    return 0;
}

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

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

    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && arr[i] == arr[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && arr[j] == arr[j - 1]) continue;
            int left = j + 1, right = n - 1;
            while (left < right) {
                int total = arr[i] + arr[j] + arr[left] + arr[right];
                if (total == target) {
                    res.push_back({arr[i], arr[j], arr[left], arr[right]});
                    left++;
                    right--;
                    while (left < right && arr[left] == arr[left - 1]) left++;
                    while (left < right && arr[right] == arr[right + 1]) right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return res;
}

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

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

    for i in range(n-3):
        if i > 0 and arr[i] == arr[i-1]:
            continue
        for j in range(i+1, n-2):
            if j > i+1 and arr[j] == arr[j-1]:
                continue
            left, right = j+1, n-1
            while left < right:
                total = arr[i] + arr[j] + arr[left] + arr[right]
                if total == target:
                    res.append([arr[i], arr[j], arr[left], arr[right]])
                    left += 1
                    right -= 1
                    while left < right and arr[left] == arr[left-1]:
                        left += 1
                    while left < right and arr[right] == arr[right+1]:
                        right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return res

arr = [1, 0, -1, 0, -2, 2]
target = 0
print("Quadruplets:", four_sum(arr, target))

import java.util.*;

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

    for (int i = 0; i < n - 3; i++) {
      if (i > 0 && arr[i] == arr[i - 1]) continue;
      for (int j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && arr[j] == arr[j - 1]) continue;
        int left = j + 1, right = n - 1;
        while (left < right) {
          int total = arr[i] + arr[j] + arr[left] + arr[right];
          if (total == target) {
            res.add(Arrays.asList(arr[i], arr[j], arr[left], arr[right]));
            left++;
            right--;
            while (left < right && arr[left] == arr[left - 1]) left++;
            while (left < right && arr[right] == arr[right + 1]) right--;
          } else if (total < target) {
            left++;
          } else {
            right--;
          }
        }
      }
    }
    return res;
  }

  public static void main(String[] args) {
    int[] arr = {1, 0, -1, 0, -2, 2};
    int target = 0;
    System.out.println("Quadruplets: " + fourSum(arr, target));
  }
}

function fourSum(arr, target) {
  arr.sort((a, b) => a - b);
  const n = arr.length;
  const res = [];

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && arr[i] === arr[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && arr[j] === arr[j - 1]) continue;
      let left = j + 1, right = n - 1;
      while (left < right) {
        const total = arr[i] + arr[j] + arr[left] + arr[right];
        if (total === target) {
          res.push([arr[i], arr[j], arr[left], arr[right]]);
          left++;
          right--;
          while (left < right && arr[left] === arr[left - 1]) left++;
          while (left < right && arr[right] === arr[right + 1]) right--;
        } else if (total < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return res;
}

const arr = [1, 0, -1, 0, -2, 2];
const target = 0;
console.log("Quadruplets:", fourSum(arr, target));

package main

import (
    "fmt"
    "sort"
)

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    n := len(nums)

    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            left, right := j+1, n-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                if sum == target {
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
                    left++
                    right--
                    for left < right && nums[left] == nums[left-1] {
                        left++
                    }
                    for left < right && nums[right] == nums[right+1] {
                        right--
                    }
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return res
}

func main() {
    arr := []int{1, 0, -1, 0, -2, 2}
    target := 0
    result := fourSum(arr, target)
    fmt.Println("Quadruplets:", result)
}

fn main() {
    let mut arr = vec![1, 0, -1, 0, -2, 2];
    let target = 0;
    let result = four_sum(&mut arr, target);
    println!("Quadruplets: {:?}", result);
}

fn four_sum(arr: &mut Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    arr.sort();
    let mut res = Vec::new();
    let n = arr.len();

    for i in 0..n-3 {
        if i > 0 && arr[i] == arr[i-1] { continue; }
        for j in i+1..n-2 {
            if j > i+1 && arr[j] == arr[j-1] { continue; }
            let mut left = j + 1;
            let mut right = n - 1;
            while left < right {
                let sum = arr[i] + arr[j] + arr[left] + arr[right];
                if sum == target {
                    res.push(vec![arr[i], arr[j], arr[left], arr[right]]);
                    left += 1;
                    right -= 1;
                    while left < right && arr[left] == arr[left-1] { left += 1; }
                    while left < right && arr[right] == arr[right+1] { right -= 1; }
                } else if sum < target {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
    }
    res
}

fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
    nums.sort()
    val res = mutableListOf<List<Int>>()
    val n = nums.size

    for (i in 0 until n - 3) {
        if (i > 0 && nums[i] == nums[i - 1]) continue
        for (j in i + 1 until n - 2) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue
            var left = j + 1
            var right = n - 1
            while (left < right) {
                val sum = nums[i] + nums[j] + nums[left] + nums[right]
                when {
                    sum == target -> {
                        res.add(listOf(nums[i], nums[j], nums[left], nums[right]))
                        left++
                        right--
                        while (left < right && nums[left] == nums[left - 1]) left++
                        while (left < right && nums[right] == nums[right + 1]) right--
                    }
                    sum < target -> left++
                    else -> right--
                }
            }
        }
    }
    return res
}

fun main() {
    val arr = intArrayOf(1, 0, -1, 0, -2, 2)
    val target = 0
    println("Quadruplets: ${fourSum(arr, target)}")
}

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  const res: number[][] = [];
  const n = nums.length;

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let left = j + 1, right = n - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          res.push([nums[i], nums[j], nums[left], nums[right]]);
          left++;
          right--;
          while (left < right && nums[left] === nums[left - 1]) left++;
          while (left < right && nums[right] === nums[right + 1]) right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }

  return res;
}

const arr = [1, 0, -1, 0, -2, 2];
const target = 0;
console.log("Quadruplets:", fourSum(arr, target));

Time complexity

Space complexity

O(1) (excluding output)

Only a few pointers and loop variables are used for the computation. However, the space needed to store the resulting quadruplets depends on the number of valid combinations found.