4 Sum | Find Quads that add up to a target value

Published : 05 October 2025

12 Views

Array Sorting Coding Problems Two Pointes

Given an array nums of integers and an integer target, return all unique quadruplets [a, b, c, d] such that:

a + b + c + d == target

The result must not contain duplicate quadruplets and the quadruplets can be in any order.

Example 1

Input:
nums = [1, 0, -1, 0, -2, 2]
target = 0

Output:
[[-2, -1, 1, 2],
 [-2, 0, 0, 2],
 [-1, 0, 0, 1]]

Example 2

Input:
nums = [2, 2, 2, 2, 2]
target = 8

Output:
[[2, 2, 2, 2]]

Constraints

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Approach 1: Brute Force Approach (4 Nested Loops)

The most straightforward way to solve the 4 Sum problem is to:

Check every possible combination of four elements in the array.
If their sum equals the target -> add that quadruplet to the result.
To avoid duplicate quadruplets (like [1,0,-1,0] vs [0,1,0,-1]), we sort each quadruplet before storing it in a Set.
This ensures all unique combinations are captured.

Steps

Loop i from 0 -> n-1
Loop j from i+1 -> n-1
Loop k from j+1 -> n-1
Loop l from k+1 -> n-1
If (nums[i] + nums[j] + nums[k] + nums[l]) == target, form a quadruplet, sort it and add it to a Set.

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

vector<vector<int>> fourSumBruteForce(vector<int>& nums, int target) {
    set<vector<int>> resultSet;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    long long sum = (long long)nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum == target) {
                        vector<int> quad = {nums[i], nums[j], nums[k], nums[l]};
                        sort(quad.begin(), quad.end());
                        resultSet.insert(quad);
                    }
                }
            }
        }
    }
    return vector<vector<int>>(resultSet.begin(), resultSet.end());
}
int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> result = fourSumBruteForce(nums, target);
    cout << "Quadruplets summing to " << target << ":\n";
    for (auto &quad : result) {
        cout << "[ ";
        for (int num : quad) cout << num << " ";
        cout << "]\n";
    }
}

import java.util.*;

public class FourSumProblem {
    public static List<List<Integer>> fourSumBruteForce(int[] nums, int target) {
        Set<List<Integer>> resultSet = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        if ((long)nums[i] + nums[j] + nums[k] + nums[l] == target) {
                            List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                            Collections.sort(quad);
                            resultSet.add(quad);
                        }
                    }
                }
            }
        }
        return new ArrayList<>(resultSet);
    }
    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> result = fourSumBruteForce(nums, target);
        System.out.println("Quadruplets summing to " + target + ":");
        for (List<Integer> quad : result) {
            System.out.println(quad);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

public class FourSumProblem {
    public static List<List<int>> FourSumBruteForce(int[] nums, int target) {
        HashSet<string> seen = new HashSet<string>();
        List<List<int>> result = new List<List<int>>();
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        long sum = (long)nums[i] + nums[j] + nums[k] + nums[l];
                        if (sum == target) {
                            var quad = new List<int> { nums[i], nums[j], nums[k], nums[l] };
                            quad.Sort();
                            string key = string.Join(",", quad);
                            if (seen.Add(key))
                                result.Add(quad);
                        }
                    }
                }
            }
        }
        return result;
    }
    public static void Main() {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        var result = FourSumBruteForce(nums, target);
        Console.WriteLine($"Quadruplets summing to {target}:");
        foreach (var quad in result) {
            Console.WriteLine("[ " + string.Join(", ", quad) + " ]");
        }
    }
}

def four_sum_brute_force(nums, target):
    n = len(nums)
    result = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                for l in range(k + 1, n):
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
                        result.add(quad)
    return [list(q) for q in result]


if __name__ == "__main__":
    nums = [1, 0, -1, 0, -2, 2]
    target = 0
    res = four_sum_brute_force(nums, target)
    print(f"Quadruplets summing to {target}:")
    for quad in res:
        print(quad)


Quadruplets summing to 0:
[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]

Complexity Analysis

Time Complexity: O(n⁴), Four nested loops
Space Complexity: O(m), For storing unique quadruplets in the set (m = number of valid results)

Approach 2: Better Approach (Using Hashing for 2-Sum Inside 4-Sum)

Instead of checking every possible quadruplet (O(n⁴)), we can fix the first two elements (i, j) and then find two remaining numbers that sum up to the required remainder.

That's exactly the 2-sum problem, which can be efficiently solved using a HashSet.

For each pair (i, j):
- The remaining target = target - (nums[i] + nums[j])
- We traverse the remaining part of the array (k onwards)
- Use a HashSet to check if remainingTarget - nums[k] exists -> if yes, we found a valid quadruplet.

Steps

Sort the array to simplify duplicate handling (though duplicates are still tricky here).
Loop i from 0 -> n-1.
Loop j from i+1 -> n-1.
Initialize a HashSet to track seen numbers for the 2-sum part.
For each k from j+1 -> n-1:
- Compute sum = nums[i] + nums[j] + nums[k]
- If (target - sum) exists in the set -> we found a quadruplet.
- Else -> add nums[k] to the set.
Store quadruplets in a Set<List> to avoid duplicates.

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

vector<vector<int>> fourSumBetter(vector<int>& nums, int target) {
    set<vector<int>> result;
    int n = nums.size();
    sort(nums.begin(), nums.end());
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            unordered_set<int> seen;
            for (int k = j + 1; k < n; k++) {
                int remaining = target - (nums[i] + nums[j] + nums[k]);
                if (seen.count(remaining)) {
                    vector<int> quad = {nums[i], nums[j], nums[k], remaining};
                    sort(quad.begin(), quad.end());
                    result.insert(quad);
                }
                seen.insert(nums[k]);
            }
        }
    }
    return vector<vector<int>>(result.begin(), result.end());
}

int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    auto res = fourSumBetter(nums, target);
    cout << "Quadruplets summing to " << target << ":\n";
    for (auto& quad : res) {
        cout << "[ ";
        for (int num : quad) cout << num << " ";
        cout << "]\n";
    }
}

import java.util.*;

public class FourSumHashing {
    public static List<List<Integer>> fourSumBetter(int[] nums, int target) {
        Set<List<Integer>> result = new HashSet<>();
        int n = nums.length;
        Arrays.sort(nums); // Helps maintain order and avoid duplicates
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Set<Integer> seen = new HashSet<>();
                for (int k = j + 1; k < n; k++) {
                    int remaining = target - (nums[i] + nums[j] + nums[k]);
                    if (seen.contains(remaining)) {
                        List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], remaining);
                        Collections.sort(quad);
                        result.add(quad);
                    }
                    seen.add(nums[k]);
                }
            }
        }
        return new ArrayList<>(result);
    }
    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> res = fourSumBetter(nums, target);
        System.out.println("Quadruplets summing to " + target + ":");
        for (List<Integer> quad : res) {
            System.out.println(quad);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

public class FourSumHashing {
    public static List<List<int>> FourSumBetter(int[] nums, int target) {
        HashSet<string> seenCombos = new HashSet<string>();
        List<List<int>> result = new List<List<int>>();
        Array.Sort(nums);
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                HashSet<int> seen = new HashSet<int>();
                for (int k = j + 1; k < n; k++) {
                    int remaining = target - (nums[i] + nums[j] + nums[k]);
                    if (seen.Contains(remaining)) {
                        var quad = new List<int> { nums[i], nums[j], nums[k], remaining };
                        quad.Sort();
                        string key = string.Join(",", quad);
                        if (seenCombos.Add(key))
                            result.Add(quad);
                    }
                    seen.Add(nums[k]);
                }
            }
        }
        return result;
    }
    public static void Main() {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        var res = FourSumBetter(nums, target);
        Console.WriteLine($"Quadruplets summing to {target}:");
        foreach (var quad in res) {
            Console.WriteLine("[ " + string.Join(", ", quad) + " ]");
        }
    }
}

def four_sum_better(nums, target):
    n = len(nums)
    nums.sort()
    result = set()
    for i in range(n):
        for j in range(i + 1, n):
            seen = set()
            for k in range(j + 1, n):
                remaining = target - (nums[i] + nums[j] + nums[k])
                if remaining in seen:
                    quad = tuple(sorted([nums[i], nums[j], nums[k], remaining]))
                    result.add(quad)
                seen.add(nums[k])
    return [list(q) for q in result]

if __name__ == "__main__":
    nums = [1, 0, -1, 0, -2, 2]
    target = 0
    res = four_sum_better(nums, target)
    print(f"Quadruplets summing to {target}:")
    for quad in res:
        print(quad)


Quadruplets summing to 0:
[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]

Complexity Analysis

Time Complexity: O(n³), Two nested loops (i, j), one traversal for k
Space Complexity: O(n), For the HashSet used in each (i, j) pair

Approach 3: Optimal Approach (Sorting + Two Pointers)

The 4 Sum problem can be efficiently solved by combining sorting and the two-pointer technique, similar to how we solve 3 Sum or 2 Sum.

Here’s the intuition:

We fix the first two numbers (i and j).
Then we use two pointers (left, right) to find the remaining two numbers whose sum completes the target.
Sorting helps in duplicate handling and allows efficient two-pointer movement based on the sum comparison.
This approach efficiently brings down time complexity from O(n⁴) to O(n³) and uses only O(1) extra space.

Step-by-Step Explanation

Sort the array , this is crucial for skipping duplicates and for pointer movement logic.
Fix the first two elements using nested loops (i and j).
Apply the two-pointer approach for the remaining two elements:
- Initialize left = j + 1 and right = n - 1
- Compute sum = nums[i] + nums[j] + nums[left] + nums[right]
- If sum equals target -> store the quadruplet and skip duplicates.
- If sum < target -> move left++ (need a bigger sum).
- If sum > target -> move right-- (need a smaller sum).
Skip duplicates for all four indices (i, j, left and right) to avoid repeated quadruplets.

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

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1, right = n - 1;
            while (left < right) {
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target)
                    left++;
                else
                    right--;
            }
        }
    }
    return result;
}
int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    auto res = fourSum(nums, target);
    cout << "Quadruplets summing to " << target << ":\n";
    for (auto& quad : res) {
        cout << "[ ";
        for (int x : quad) cout << x << " ";
        cout << "]\n";
    }
}

import java.util.*;

public class FourSumOptimal {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate i
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicate j
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> res = fourSum(nums, target);
        System.out.println("Quadruplets summing to " + target + ":");
        for (List<Integer> quad : res) {
            System.out.println(quad);
        }
    }
}

using System;
using System.Collections.Generic;

public class FourSumOptimal {
    public static List<List<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        List<List<int>> result = new List<List<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) left++;
                    else right--;
                }
            }
        }
        return result;
    }
    public static void Main() {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        var res = FourSum(nums, target);
        Console.WriteLine($"Quadruplets summing to {target}:");
        foreach (var quad in res) {
            Console.WriteLine("[ " + string.Join(", ", quad) + " ]");
        }
    }
}

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

if __name__ == "__main__":
    nums = [1, 0, -1, 0, -2, 2]
    target = 0
    result = four_sum(nums, target)
    print(f"Quadruplets summing to {target}:")
    for quad in result:
        print(quad)


Quadruplets summing to 0:
[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]

Complexity Analysis

Time Complexity: O(n³), Double loops for i, j and two-pointer traversal
Space Complexity: O(1), Only uses result list, no extra data structure
Sorting Overhead: O(n log n), Negligible compared to O(n³) main loop

Complexity Analysis

Approach	Time Complexity	Space Complexity	Notes
Brute Force (4 loops)	O(n⁴)	O(n)	Too slow
Hashing-based 3-loop	O(n³)	O(n)	Better but still heavy
Sorting + Two Pointers (Optimal)	O(n³)	O(1)	Best approach