4Sum: Find All Unique Quadruplets with a Target Sum

103.4k
0

Given an integer array nums and an integer target, find all unique quadruplets whose sum is equal to target.

A quadruplet means four different elements from the array.

The answer should not contain duplicate quadruplets.

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]]

Explanation: These three unique quadruplets have sum 0. Duplicate quadruplets are not included.

Example 2

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

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

Explanation: The quadruplet [2, 2, 2, 2] has sum 8. Even though many combinations are possible, the same quadruplet is included only once.

Brute Force Approach

Every possible group of four different indices can be examined directly. Four nested loops generate each index combination once by maintaining first < second < third < fourth.

Duplicate values may produce the same quadruplet through different index combinations. Sorting every valid quadruplet creates one consistent value order, while a set keeps only unique combinations. Complete enumeration remains straightforward but becomes expensive for large arrays.

Algorithm

  • Store the array size in n. If n < 4, return an empty answer because four different indices are required to form a quadruplet.

  • Create uniqueQuadruplets to store valid value combinations without allowing duplicate quadruplets in the final result.

  • Use first, second, third, and fourth such that first < second < third < fourth. This generates every group of four different indices exactly once.

  • Calculate the sum of the four selected values using 64-bit arithmetic so large integer values do not overflow during addition.

  • If the sum equals target, sort the four selected values before inserting them into uniqueQuadruplets, giving duplicate value combinations the same representation.

  • Copy all distinct quadruplets from uniqueQuadruplets into the answer and return it after every index combination has been checked.

Dry Run

4 sum Brute Force Appraoch Dry Run

4 sum Brute Force Appraoch Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
// Four different indices are required.
if (n < 4) {
return {};
}
set<vector<int>> uniqueQuadruplets;
/*
* Generate every combination of four
* different indices exactly once.
*/
for (int first = 0; first < n - 3; first++) {
for (int second = first + 1; second < n - 2; second++) {
for (int third = second + 1; third < n - 1; third++) {
for (int fourth = third + 1; fourth < n; fourth++) {
long long sum =
(long long) nums[first] +
nums[second] +
nums[third] +
nums[fourth];
// A matching sum gives a valid quadruplet.
if (sum == target) {
vector<int> quadruplet = {
nums[first],
nums[second],
nums[third],
nums[fourth]
};
/*
* Sorting gives duplicate quadruplets
* the same arrangement.
*/
sort(quadruplet.begin(), quadruplet.end());
uniqueQuadruplets.insert(quadruplet);
}
}
}
}
}
return vector<vector<int>>(
uniqueQuadruplets.begin(),
uniqueQuadruplets.end()
);
}
};
int main() {
vector<int> nums = {1, 0, -1, 0, -2, 2};
int target = 0;
Solution solution;
vector<vector<int>> answer = solution.fourSum(nums, target);
for (const auto& quadruplet : answer) {
for (int value : quadruplet) {
cout << value << " ";
}
cout << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N⁴), where N represents the array size.

Space Complexity: O(M), where M represents the number of unique quadruplets stored for duplicate removal.

Better Approach

The Brute Force Approach uses a fourth loop to search for the final value. After selecting three values, only one specific fourth value can complete the target sum.

For selected values nums[first], nums[second], and nums[third], the required fourth value equals target - nums[first] - nums[second] - nums[third]. A hash set stores values already visited during the current fixed-pair traversal, allowing average constant-time lookup for the required value.

Algorithm

  • Store the array size in n. If n < 4, return an empty answer because a quadruplet requires four different positions.

  • Create uniqueQuadruplets for duplicate removal, and use first and second to fix the first two indices of the current quadruplet.

  • For every fixed pair, create a fresh seenValues set. It stores values encountered at earlier positions during the search for the remaining two elements.

  • Move third from second + 1 to n - 1 and calculate
    fourthValue = target - nums[first] - nums[second] - nums[third]
    using 64-bit arithmetic.

  • If fourthValue already exists in seenValues, the required fourth element comes from an earlier, different index. Sort the four values and insert the quadruplet into uniqueQuadruplets.

  • Insert nums[third] into seenValues only after the lookup so the current index cannot be reused. Return all distinct quadruplets after the traversals finish.

Dry Run

4 sum Better Appraoch Dry Run.png

4 sum Better Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
// Four different indices are required.
if (n < 4) {
return {};
}
set<vector<int>> uniqueQuadruplets;
for (int first = 0; first < n - 3; first++) {
for (int second = first + 1; second < n - 2; second++) {
unordered_set<long long> seenValues;
/*
* Values seen earlier can act as
* the fourth element of a quadruplet.
*/
for (int third = second + 1; third < n; third++) {
long long fourthValue =
(long long) target -
nums[first] -
nums[second] -
nums[third];
/*
* A previously seen required value
* completes the target sum.
*/
if (seenValues.find(fourthValue) !=
seenValues.end()) {
vector<int> quadruplet = {
nums[first],
nums[second],
nums[third],
(int) fourthValue
};
sort(quadruplet.begin(), quadruplet.end());
uniqueQuadruplets.insert(quadruplet);
}
/*
* Insert after lookup so the current
* index cannot be reused.
*/
seenValues.insert(nums[third]);
}
}
}
return vector<vector<int>>(
uniqueQuadruplets.begin(),
uniqueQuadruplets.end()
);
}
};
int main() {
vector<int> nums = {1, 0, -1, 0, -2, 2};
int target = 0;
Solution solution;
vector<vector<int>> answer = solution.fourSum(nums, target);
for (const auto& quadruplet : answer) {
for (int value : quadruplet) {
cout << value << " ";
}
cout << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N³) on average, where N represents the array size.

Space Complexity: O(N + M), where seenValues may store O(N) values and uniqueQuadruplets may store M distinct quadruplets.

Optimal Approach

Sorting places smaller values toward the left and larger values toward the right. After fixing two values, the remaining task becomes finding two additional values whose sum completes target.

Pointer left begins immediately after the second fixed index, while pointer right begins at the final index. A total smaller than target requires a larger value, so left moves forward. A total greater than target requires a smaller value, so right moves backward. Sorted order also places duplicate values together, allowing direct duplicate skipping without a result set.

Algorithm

  • Store the array size in n. If n < 4, return an empty answer. Sort nums so pointer movement and duplicate handling become possible.

  • Traverse first from index 0 to n - 4. Skip it when first > 0 and nums[first] == nums[first - 1], because the same first value has already been processed.

  • For each first, traverse second from first + 1 to n - 3. Skip repeated second values within the current first traversal to avoid generating duplicate quadruplets.

  • Initialize left = second + 1 and right = n - 1, then calculate the four-value sum using 64-bit arithmetic.

  • If the sum is smaller than target, move left forward to increase it. If the sum is greater, move right backward to decrease it. If the sum matches, add the current quadruplet to the answer.

  • After finding a valid quadruplet, move both pointers inward and skip repeated values at left and right. Return the answer after all fixed pairs have been processed.

Dry Run

4 sum Optimal Appraoch Dry Run.png

4 sum Optimal Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> answer;
// Four different indices are required.
if (n < 4) {
return answer;
}
sort(nums.begin(), nums.end());
for (int first = 0; first < n - 3; first++) {
/*
* Skip a repeated first value to avoid
* generating duplicate quadruplets.
*/
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
for (int second = first + 1; second < n - 2; second++) {
/*
* Skip repeated second values only
* within the current first value.
*/
if (second > first + 1 &&
nums[second] == nums[second - 1]) {
continue;
}
int left = second + 1;
int right = n - 1;
while (left < right) {
long long sum =
(long long) nums[first] +
nums[second] +
nums[left] +
nums[right];
// A smaller sum needs a larger left value.
if (sum < target) {
left++;
}
// A larger sum needs a smaller right value.
else if (sum > target) {
right--;
}
else {
answer.push_back({
nums[first],
nums[second],
nums[left],
nums[right]
});
left++;
right--;
/*
* Skip repeated boundary values
* to avoid duplicate answers.
*/
while (left < right &&
nums[left] == nums[left - 1]) {
left++;
}
while (left < right &&
nums[right] == nums[right + 1]) {
right--;
}
}
}
}
}
return answer;
}
};
int main() {
vector<int> nums = {1, 0, -1, 0, -2, 2};
int target = 0;
Solution solution;
vector<vector<int>> answer = solution.fourSum(nums, target);
for (const auto& quadruplet : answer) {
for (int value : quadruplet) {
cout << value << " ";
}
cout << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N³), where N represents the array size. Sorting takes O(N log N), while the two fixed loops with the two-pointer traversal require O(N³) time.

Space Complexity: O(1) when output storage is excluded. Internal sorting may require implementation-dependent memory.

FAQs

Q1. Can one array position appear more than once inside a quadruplet?

No. Every quadruplet requires four different indices, although equal values from separate indices remain valid.

Q2. Why must valid quadruplets be unique by value rather than by index?

Different index combinations may contain the same four values. The final answer requires unique value combinations.

Q3. How does the Better Approach remove the fourth loop?

After selecting three values, only one fourth value can complete target. Hash-set lookup searches for the required value in average constant time.

Q4. Why does seenValues receive nums[third] after lookup?

Insertion after lookup guarantees a different earlier index for the required fourth value and prevents reuse of the current third index.

Q5. Why does the Optimal Approach skip duplicate values?

Sorted duplicates appear beside one another. Skipping repeated first, second, left, and right values prevents insertion of the same quadruplet more than once.

Q6. Why should four-value sums use 64-bit arithmetic?

Adding four large integer values may exceed the 32-bit integer range. A 64-bit sum prevents overflow and incorrect comparisons with target.

ArraysTwo Pointer

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.6k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0