Four Sum Problem All Unique Quadruplets in DSA C++

Mental Model

Find four numbers in a list that add up to a target without repeating the same group twice.

Analogy: Imagine you have a box of different colored balls and want to pick exactly four balls that together weigh a certain amount, but you never want to pick the same combination twice.

Array: [1, 0, -1, 0, -2, 2]
Indices:  0  1   2  3   4   5
Goal: Find quadruplets that sum to 0

Dry Run Walkthrough

Input: list: [1, 0, -1, 0, -2, 2], target: 0

Goal: Find all unique sets of four numbers that add up to 0

Step 1: Sort the array to make it easier to find quadruplets

[-2, -1, 0, 0, 1, 2]

Why: Sorting helps to avoid duplicates and use two-pointer technique efficiently

Step 2: Fix first number at index 0 (-2), then fix second number at index 1 (-1)

[-2, -1, 0, 0, 1, 2] ↑i=0 ↑j=1

Why: We pick first two numbers and look for remaining two numbers that sum to target minus these

Step 3: Use two pointers left=2 (0) and right=5 (2) to find pairs that sum to 3 (0 - (-2 + -1))

[-2, -1, 0, 0, 1, 2] i=0 j=1 left=2 right=5

Why: Two pointers help find pairs efficiently without checking all pairs

Step 4: Sum is -2 + -1 + 0 + 2 = -1, less than target 0, move left pointer right

[-2, -1, 0, 0, 1, 2] i=0 j=1 left=3 right=5

Why: Sum too small, increase sum by moving left pointer right

Step 5: Sum is -2 + -1 + 0 + 2 = -1 again, move left pointer right

[-2, -1, 0, 0, 1, 2] i=0 j=1 left=4 right=5

Why: Still less than target, move left pointer to increase sum

Step 6: Sum is -2 + -1 + 1 + 2 = 0, quadruplet found [-2, -1, 1, 2]

[-2, -1, 0, 0, 1, 2]

Why: Sum matches target, record quadruplet and move pointers to find more

Step 7: Move left pointer to 5 and right pointer to 4, pointers cross, move second number to index 2

[-2, -1, 0, 0, 1, 2] i=0 j=2

Why: No more pairs for this second number, move to next second number

Step 8: Repeat two pointer search for i=0, j=2 (0), left=3 (0), right=5 (2)

[-2, -1, 0, 0, 1, 2] i=0 j=2 left=3 right=5

Why: Find pairs that sum to 0 - (-2 + 0) = 2

Step 9: Sum is -2 + 0 + 0 + 2 = 0, quadruplet found [-2, 0, 0, 2]

[-2, -1, 0, 0, 1, 2]

Why: Sum matches target, record quadruplet

Step 10: Move left and right pointers, no more pairs, move first number to index 1

[-2, -1, 0, 0, 1, 2] i=1

Why: Finished all pairs for i=0, move to next first number

Step 11: Fix i=1 (-1), j=2 (0), left=3 (0), right=5 (2), target sum for pairs is 0 - (-1 + 0) = 1

[-2, -1, 0, 0, 1, 2] i=1 j=2 left=3 right=5

Why: Find pairs that sum to 1

Step 12: Sum is -1 + 0 + 0 + 2 = 1, quadruplet found [-1, 0, 0, 2]

[-2, -1, 0, 0, 1, 2]

Why: Sum matches target, record quadruplet

Step 13: Move pointers, sum no longer matches, finish search

[-2, -1, 0, 0, 1, 2]

Why: No more quadruplets found

Result:

[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    int n = nums.size();
    sort(nums.begin(), nums.end());
    for (int i = 0; i < n - 3; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for i
        for (int j = i + 1; j < n - 2; ++j) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates for j
            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]});
                    // skip duplicates for left
                    while (left < right && nums[left] == nums[left + 1]) ++left;
                    // skip duplicates for right
                    while (left < right && nums[right] == nums[right - 1]) --right;
                    ++left;
                    --right;
                } else if (sum < target) {
                    ++left; // increase sum
                } else {
                    --right; // decrease sum
                }
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    vector<vector<int>> quadruplets = fourSum(nums, target);
    for (auto& quad : quadruplets) {
        cout << quad[0] << ", " << quad[1] << ", " << quad[2] << ", " << quad[3] << "\n";
    }
    return 0;
}

sort(nums.begin(), nums.end());

sort array to enable two-pointer technique and duplicate skipping

if (i > 0 && nums[i] == nums[i - 1]) continue;

skip duplicate first numbers to avoid repeated quadruplets

if (j > i + 1 && nums[j] == nums[j - 1]) continue;

skip duplicate second numbers to avoid repeated quadruplets

while (left < right) {

use two pointers to find pairs that complete quadruplet

long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];

calculate sum of current quadruplet candidates

if (sum == target) {

found quadruplet matching target sum

while (left < right && nums[left] == nums[left + 1]) ++left;

skip duplicates for left pointer

while (left < right && nums[right] == nums[right - 1]) --right;

skip duplicates for right pointer

++left; --right;

move pointers inward to find new pairs

else if (sum < target) { ++left; } else { --right; }

adjust pointers to increase or decrease sum

Output

-2, -1, 1, 2

-2, 0, 0, 2

-1, 0, 0, 1

Complexity Analysis

Time: O(n^3) because we use two nested loops and a two-pointer scan inside

Space: O(k) where k is number of quadruplets found, for storing results

vs Alternative: Better than naive O(n^4) which checks all quadruplets; sorting and two pointers reduce complexity

Edge Cases

empty array

returns empty list, no quadruplets found

DSA C++

for (int i = 0; i < n - 3; ++i) {

array with fewer than 4 elements

returns empty list, no quadruplets possible

DSA C++

for (int i = 0; i < n - 3; ++i) {

array with duplicates

duplicates skipped to avoid repeated quadruplets

DSA C++

if (i > 0 && nums[i] == nums[i - 1]) continue;

When to Use This Pattern

When asked to find unique quadruplets summing to a target, use sorting plus two nested loops and two pointers to efficiently find all sets without duplicates.

Common Mistakes

Mistake: Not sorting the array before processing
Fix: Sort the array first to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for i, j, left, or right pointers
Fix: Add checks to skip duplicates after sorting to avoid repeated quadruplets

Mistake: Using int sum without casting to long long causing overflow
Fix: Cast sum calculation to long long to prevent integer overflow

Summary

Finds all unique sets of four numbers in an array that add up to a target sum.

Use when you need to find quadruplets summing to a target without duplicates efficiently.

Sort the array and use two nested loops plus two pointers to find quadruplets while skipping duplicates.

Practice

1. What is the main goal of the Four Sum Problem in data structures and algorithms?

easy

A. Find all unique quadruplets in an array that sum up to a target value

B. Sort the array in ascending order

C. Find the maximum element in the array

D. Count the number of pairs with a given sum

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks to find all unique sets of four numbers in an array that add up to a specific target sum.

2. Step 2: Identify the goal

   The goal is to find quadruplets (groups of four numbers) that sum exactly to the target, without duplicates.

3. Final Answer:

   Find all unique quadruplets in an array that sum up to a target value -> Option A

4. Quick Check:

   Four Sum Problem = Find quadruplets summing to target [OK]

Hint: Look for four numbers adding to target without repeats [OK]

Common Mistakes:

• Confusing with pair or triplet sum problems
• Ignoring uniqueness of quadruplets
• Trying to sort only without finding quadruplets

2. Which of the following C++ code snippets correctly initializes a vector to store quadruplets for the Four Sum Problem?

easy

A. std::vector<int> quadruplets(4);

B. std::vector quadruplets;

C. std::vector<int> quadruplets = {4};

D. std::vector> quadruplets;

Solution

1. Step 1: Understand the data structure needed

   We need to store multiple quadruplets, each is a vector of 4 integers, so a vector of vector<int> is suitable.

2. Step 2: Check each option

   std::vector quadruplets; declares a vector of vector<int>, perfect for storing multiple quadruplets. std::vector<int> quadruplets(4); creates a single vector of size 4, not multiple quadruplets. std::vector<int> quadruplets = {4}; initializes a vector with one element 4, incorrect. std::vector> quadruplets; uses pairs, which store only two integers, not four.

3. Final Answer:

   std::vector quadruplets; -> Option B

4. Quick Check:

   Use vector of vector<int> for quadruplets [OK]

Hint: Use vector of vector<int> to store multiple quadruplets [OK]

Common Mistakes:

• Using vector<int> for multiple quadruplets
• Using pairs instead of quadruplets
• Initializing vector with wrong size or values

3. What will be the output of the following C++ code snippet for input array {1, 0, -1, 0, -2, 2} and target 0?

std::vector<int> nums = {1, 0, -1, 0, -2, 2};
int target = 0;
// Assume fourSum function returns all unique quadruplets
auto result = fourSum(nums, target);
for (auto &quad : result) {
    for (int num : quad) std::cout << num << " ";
    std::cout << std::endl;
}

medium

A. [-2 -1 1 2]
[-2 0 0 2]
[-1 0 0 1]

B. [-2 -1 0 1]
[-1 0 0 2]

C. [-2 -2 1 3]
[-1 0 0 1]

D. No quadruplets found

Solution

1. Step 1: Sort the array and find quadruplets summing to target 0

   Sorted array: [-2, -1, 0, 0, 1, 2]. The unique quadruplets summing to 0 are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

2. Step 2: Verify output matches quadruplets

   [-2 -1 1 2] [-2 0 0 2] [-1 0 0 1] lists exactly these three quadruplets. Options A, C, and D have incorrect quadruplets or sums.

3. Final Answer:

   [-2 -1 1 2] [-2 0 0 2] [-1 0 0 1] -> Option A

4. Quick Check:

   Unique quadruplets summing to 0 = [-2 -1 1 2] [-2 0 0 2] [-1 0 0 1] [OK]

Hint: Sort array first, then find quadruplets summing to target [OK]

Common Mistakes:

• Not sorting array before searching
• Including duplicate quadruplets
• Missing some valid quadruplets

4. Identify the bug in the following C++ code snippet for the Four Sum Problem:

std::vector fourSum(std::vector<int>& nums, int target) {
    std::vector result;
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size(); ++j) {
            int left = j + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                    ++left; --right;
                } else if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
    }
    return result;
}

medium

A. Returns result before completing loops

B. Incorrect sorting of the input array

C. Wrong initialization of left and right pointers

D. Does not skip duplicate quadruplets, causing repeated results

Solution

1. Step 1: Analyze duplicate handling in loops

   The code does not skip duplicates for i, j, left, or right indices, so it can add the same quadruplet multiple times.

2. Step 2: Check other parts for errors

   Sorting is correct, left and right pointers are initialized properly, and return is after loops. So these are not bugs.

3. Final Answer:

   Does not skip duplicate quadruplets, causing repeated results -> Option D

4. Quick Check:

   Missing duplicate checks = Does not skip duplicate quadruplets, causing repeated results [OK]

Hint: Always skip duplicates after finding quadruplets [OK]

Common Mistakes:

• Not skipping duplicates for i, j, left, right
• Returning result too early
• Incorrect pointer initialization

5. Given an array nums = {2, 2, 2, 2, 2} and target 8, how many unique quadruplets does the Four Sum algorithm find, and what are they?

hard

A. 10 quadruplets: including duplicates

B. 5 quadruplets: all combinations of 2s

C. 1 quadruplet: [2, 2, 2, 2]

D. 0 quadruplets: no quadruplets sum to 8

Solution

1. Step 1: Understand the input and target

   All elements are 2, and target is 8. Sum of four 2s is 8, so quadruplet [2, 2, 2, 2] is valid.

2. Step 2: Consider uniqueness

   Even though multiple combinations exist, they are duplicates. The algorithm returns only one unique quadruplet.

3. Final Answer:

   1 quadruplet: [2, 2, 2, 2] -> Option C

4. Quick Check:

   All 2s sum to 8 once uniquely [OK]

Hint: Duplicates count as one unique quadruplet [OK]

Common Mistakes:

• Counting duplicate quadruplets multiple times
• Assuming no quadruplets because of repeated numbers
• Confusing number of combinations with unique quadruplets