Four Sum Problem All Unique Quadruplets in DSA C++ - Deep Dive

Overview - Four Sum Problem All Unique Quadruplets

What is it?

The Four Sum Problem asks us to find all unique groups of four numbers in a list that add up to a specific target number. Each group of four numbers is called a quadruplet. The goal is to list all such quadruplets without repeating any. This problem helps us understand how to efficiently search combinations in arrays.

Why it matters

Without a method like this, finding all quadruplets that sum to a target would require checking every possible group of four numbers, which takes a very long time for large lists. This problem teaches us how to reduce that time by sorting and using pointers, making it practical to solve in real situations like financial data analysis or game scoring. Without it, many real-world problems involving combinations would be too slow to solve.

Where it fits

Before this, you should understand arrays, sorting, and the two-pointer technique. After mastering Four Sum, you can learn more complex combination problems like k-Sum or explore hashing techniques for faster lookups.

Mental Model

Core Idea

Find four numbers that add up to the target by fixing two numbers and searching for the other two using two pointers in a sorted list to avoid duplicates efficiently.

Think of it like...

Imagine you are at a party trying to find four friends whose ages add up to a certain number. You first pick two friends and then look for two others who fit the age sum perfectly, moving closer or farther in the room based on whether the sum is too low or too high.

Sorted Array: [a1, a2, a3, ..., an]
Fix i -> a[i]
  Fix j -> a[j] (j > i)
    Use two pointers: left = j+1, right = n-1
      While left < right:
        sum = a[i] + a[j] + a[left] + a[right]
        if sum == target -> record quadruplet
        if sum < target -> left++
        else -> right--
Avoid duplicates by skipping equal values at i, j, left, right

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the Four Sum problem asks and what a quadruplet is.

Given an array of numbers and a target sum, find all unique sets of four numbers that add up exactly to the target. Each set is called a quadruplet. The array can have duplicates, but the output should not contain duplicate quadruplets.

Result

Clear understanding of the problem goal and constraints.

Understanding the problem clearly prevents confusion about what counts as a valid answer and what duplicates mean.

2

Foundation

Sorting the Array for Order

Concept: Sort the array to make searching and skipping duplicates easier.

Sort the input array in ascending order. This helps us use the two-pointer technique and easily skip over duplicate numbers to avoid repeated quadruplets.

Result

A sorted array that allows efficient searching and duplicate handling.

Sorting is a key step that transforms the problem into a structured search, enabling faster and cleaner solutions.

3

Intermediate

Using Two Nested Loops to Fix Two Numbers

🤔Before reading on: Do you think fixing two numbers first reduces the problem complexity? Commit to yes or no.

Concept: Fix two numbers with nested loops to reduce the problem to finding two numbers that sum to a new target.

Use two loops: the outer loop picks the first number (index i), the inner loop picks the second number (index j) where j > i. For each pair (a[i], a[j]), we look for two more numbers that sum to target - (a[i] + a[j]).

Result

Problem reduces from four numbers to two numbers search for each fixed pair.

Fixing two numbers breaks the problem into smaller parts, making it easier to apply the two-pointer search for the remaining two numbers.

4

Intermediate

Applying Two-Pointer Technique for Remaining Pair

🤔Before reading on: Will moving pointers inward help find pairs summing to the target? Commit to yes or no.

Concept: Use two pointers starting from both ends of the remaining array segment to find pairs that sum to the required value.

Set left pointer at j+1 and right pointer at end of array. Calculate current sum with fixed numbers plus a[left] + a[right]. If sum equals target, record quadruplet and move pointers skipping duplicates. If sum less than target, move left pointer right to increase sum. If sum greater, move right pointer left to decrease sum.

Result

Efficiently find all pairs that complete quadruplets without checking all pairs explicitly.

Two-pointer technique leverages sorted order to find pairs in linear time, drastically reducing complexity.

5

Intermediate

Skipping Duplicates to Ensure Unique Quadruplets

🤔Before reading on: Do you think skipping duplicates is necessary to avoid repeated quadruplets? Commit to yes or no.

Concept: Skip over numbers equal to the previous one at each step to avoid duplicate quadruplets in the result.

After sorting, when moving i, j, left, or right pointers, if the current number is the same as the previous one, skip it. This prevents adding the same quadruplet multiple times.

Result

Output contains only unique quadruplets with no repeats.

Skipping duplicates is crucial to meet problem requirements and avoid redundant work.

6

Advanced

Time Complexity and Optimization Insights

🤔Before reading on: Do you think this approach runs in less than O(n^4)? Commit to yes or no.

Concept: Analyze the time complexity and understand why this approach is more efficient than brute force.

Brute force checks all quadruplets in O(n^4). Sorting plus two nested loops plus two-pointer search reduces it to O(n^3). This is because for each pair fixed by i and j, the two-pointer search runs in O(n).

Result

Understanding that the solution is cubic time, which is practical for moderate input sizes.

Knowing the complexity helps set expectations and guides when this solution is feasible.

7

Expert

Handling Integer Overflow and Edge Cases

🤔Before reading on: Should we worry about integer overflow when summing four numbers? Commit to yes or no.

Concept: Consider integer overflow and edge cases like empty arrays, very large or small numbers, and duplicates at boundaries.

In C++, summing four integers might overflow int range. Use long long or careful checks. Also handle cases where array size is less than 4 by returning empty result. Ensure skipping duplicates works correctly at array ends.

Result

Robust solution that works correctly on all valid inputs without errors or crashes.

Anticipating edge cases and overflow prevents subtle bugs that can cause wrong answers or crashes in production.

Under the Hood

The algorithm first sorts the array to arrange numbers in ascending order. It then uses two nested loops to fix the first two numbers of the quadruplet. For the remaining two numbers, it uses two pointers starting from both ends of the subarray after the second fixed number. By moving these pointers inward based on the sum compared to the target, it efficiently finds pairs that complete the quadruplet. Duplicate quadruplets are avoided by skipping repeated numbers at each step. Internally, this reduces the search space from O(n^4) to O(n^3).

Why designed this way?

The problem is designed to find combinations efficiently. Sorting enables the two-pointer technique, which is faster than brute force. Fixing two numbers reduces the problem dimension, making it manageable. Skipping duplicates ensures the output meets uniqueness requirements. Alternatives like hashing exist but can be more complex or use more memory. This approach balances simplicity, speed, and memory use.

Input Array (unsorted)
      ↓ sort
Sorted Array: a[0] ... a[n-1]
  ┌─────────────┐
  │ Outer loop i│
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Inner loop j│
  └─────────────┘
        ↓
  ┌─────────────────────────────┐
  │ Two pointers: left, right    │
  │ left = j+1, right = n-1      │
  │ Move pointers based on sum   │
  └─────────────────────────────┘
        ↓
  Collect quadruplets if sum == target
        ↓
  Skip duplicates at i, j, left, right
        ↓
  Output unique quadruplets

Myth Busters - 4 Common Misconceptions

Quick: Does sorting the array change the quadruplets you can find? Commit to yes or no.

Common Belief: Sorting the array might change the quadruplets or lose some combinations.

Reality: Sorting only rearranges the order but does not change the numbers or their sums. All quadruplets still exist, just in sorted order.

Why it matters: Believing sorting changes results might stop learners from using the efficient two-pointer method, leading to slower solutions.

Quick: Is it okay to add quadruplets without checking for duplicates? Commit to yes or no.

Common Belief: You can add all quadruplets found without worrying about duplicates; duplicates are rare.

Reality: Duplicates are common especially with repeated numbers. Not skipping duplicates leads to repeated quadruplets in output.

Why it matters: Ignoring duplicates causes incorrect answers and wastes time processing repeated results.

Quick: Does the two-pointer technique work on unsorted arrays? Commit to yes or no.

Common Belief: Two-pointer technique works regardless of array order.

Reality: Two-pointer requires a sorted array to decide pointer moves based on sum comparisons.

Why it matters: Trying two-pointer on unsorted arrays leads to wrong answers and confusion.

Quick: Can integer overflow be ignored when summing four integers? Commit to yes or no.

Common Belief: Integer overflow is not a concern for this problem because numbers are small.

Reality: Input numbers can be large, and summing four can overflow int range in C++.

Why it matters: Ignoring overflow can cause wrong sums and incorrect quadruplets, leading to bugs in real applications.

Expert Zone

1

When skipping duplicates, it is important to do so immediately after processing a valid quadruplet and also when moving the i and j indices to avoid subtle repeated quadruplets.

2

Using long long for sum calculations prevents overflow but may slightly slow down the program; balancing safety and performance is key in production.

3

Early termination checks can be added: if the smallest possible sum with current i and j is greater than target, or the largest possible sum is less than target, skip iterations to save time.

When NOT to use

This approach is not ideal for very large arrays where n^3 is still too slow. In such cases, hashing-based methods or approximate algorithms might be better. Also, if the problem requires counting quadruplets rather than listing them, specialized counting algorithms are preferred.

Production Patterns

In production, this pattern is used in financial fraud detection to find suspicious combinations of transactions, in gaming to find scoring combinations, and in recommendation systems to find sets of items matching criteria. It is often combined with early pruning and parallel processing for speed.

Connections

Two Sum Problem

Builds-on

Understanding Two Sum helps grasp the two-pointer search for pairs in Four Sum, as Four Sum reduces to multiple Two Sum problems.

k-Sum Problem

Generalization

Four Sum is a special case of k-Sum where k=4; learning Four Sum prepares you to solve k-Sum with recursion or iterative approaches.

Subset Sum Problem (Computer Science)

Related problem

Both problems involve finding subsets that sum to a target, but Subset Sum focuses on any size subset and is NP-complete, highlighting the complexity jump beyond fixed-size sums.

Common Pitfalls

#1 Not skipping duplicates leads to repeated quadruplets in output.

Wrong approach:

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int left = j + 1, right = n - 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--;
}
}
}
}

Correct approach:

for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; 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--;
}
}
}
}

Root cause:

Not understanding the importance of skipping duplicates at each step causes repeated quadruplets.

#2 Using int type for sum causes overflow with large numbers.

Wrong approach:

int sum = nums[i] + nums[j] + nums[left] + nums[right];

Correct approach:

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

Root cause:

Ignoring integer overflow risks when summing multiple integers.

#3 Applying two-pointer technique on unsorted array.

Wrong approach:

int left = j + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
// move pointers without sorting
}

Correct approach:

sort(nums.begin(), nums.end());
int left = j + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
// move pointers based on sum
}

Root cause:

Not sorting the array before using two-pointer breaks the logic of pointer movement.

Key Takeaways

The Four Sum problem finds all unique quadruplets in an array that sum to a target by fixing two numbers and searching for the other two with two pointers.

Sorting the array is essential to apply the two-pointer technique and to skip duplicates efficiently.

Skipping duplicates at every step ensures the output contains only unique quadruplets without repetition.

This approach reduces the time complexity from O(n^4) to O(n^3), making it practical for moderate input sizes.

Handling edge cases like integer overflow and empty inputs is crucial for a robust solution.

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