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. We want to list all such quadruplets without repeating any group. This problem helps us practice searching and combining numbers efficiently.

Why it matters

Without a method like this, finding all quadruplets that sum to a target would take a very long time, especially with large lists. This problem teaches us how to reduce unnecessary work and avoid duplicates, which is important in many real-world tasks like data analysis and searching combinations. Without it, programs would be slow and inefficient.

Where it fits

Before this, you should understand arrays, sorting, and the two-pointer technique. After mastering this, you can learn more complex combination problems like k-sum or optimization problems involving sums.

Mental Model

Core Idea

Find four numbers that add to the target by fixing two numbers and searching for the other two using a two-pointer approach on a sorted list.

Think of it like...

Imagine you have a group of friends and want to find all unique teams of four whose combined ages add up to a birthday milestone. You first pick two friends, then look for two others who complete the team perfectly without repeating any team.

Sorted array: [a1, a2, a3, ..., an]
Fix i from 0 to n-4
  Fix j from i+1 to n-3
    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, move pointers skipping duplicates
      else if sum < target: left++
      else: right--

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the problem asks: find all unique sets of four numbers summing to a target.

Given an array of integers and a target number, we want to find all unique quadruplets (four numbers) that add up exactly to the target. The quadruplets should not repeat even if the numbers appear multiple times in the array.

Result

Clear understanding of the problem goal and constraints.

Knowing exactly what to find helps avoid confusion and guides the approach to solve the problem.

2

Foundation

Sorting the Array for Easier Searching

Concept: Sort the array to make it easier to find quadruplets and avoid duplicates.

Sorting arranges numbers in order. This helps us use two pointers to find pairs quickly and skip duplicates by comparing neighbors.

Result

Sorted array ready for efficient searching.

Sorting transforms the problem into a structured search, reducing complexity and enabling duplicate checks.

3

Intermediate

Fixing Two Numbers and Searching for Two

🤔Before reading on: Do you think fixing one number and searching for three is easier or fixing two and searching for two? Commit to your answer.

Concept: Fix two numbers and then find the other two using two pointers.

We use two loops to fix the first two numbers (i and j). Then, we use two pointers (left and right) to find pairs that complete the quadruplet to the target sum.

Result

A method to reduce the problem from four numbers to two numbers search.

Breaking the problem into smaller parts simplifies the search and improves efficiency.

4

Intermediate

Skipping Duplicates to Ensure Unique Quadruplets

🤔Before reading on: Should we skip duplicates before or after finding quadruplets? Commit to your answer.

Concept: Avoid repeating the same quadruplet by skipping duplicate numbers during iteration.

After sorting, if the current number is the same as the previous one, we skip it to avoid duplicate quadruplets. This applies to all four indices: i, j, left, and right.

Result

Only unique quadruplets are recorded.

Skipping duplicates prevents redundant work and ensures the output is clean and correct.

5

Intermediate

Two-Pointer Technique for Pair Searching

Concept: Use two pointers moving inward to find pairs that sum to a target efficiently.

With left starting at j+1 and right at the end, we calculate the sum with fixed i and j. If sum is less than target, move left forward to increase sum. If more, move right backward to decrease sum. When equal, record quadruplet and move pointers skipping duplicates.

Result

Pairs found in O(n) time instead of O(n^2).

Two pointers exploit sorted order to find pairs quickly without checking all pairs.

6

Advanced

Complete C Code Implementation

🤔Before reading on: Do you think the code should handle empty arrays and duplicates explicitly? Commit to your answer.

Concept: Putting all ideas together into a working C program that finds all unique quadruplets.

#include #include int cmpfunc(const void *a, const void *b) { return (*(int*)a - *(int*)b); } void fourSum(int* nums, int numsSize, int target) { if (numsSize < 4) return; qsort(nums, numsSize, sizeof(int), cmpfunc); for (int i = 0; i < numsSize - 3; i++) { if (i > 0 && nums[i] == nums[i-1]) continue; // skip duplicates for (int j = i + 1; j < numsSize - 2; j++) { if (j > i + 1 && nums[j] == nums[j-1]) continue; // skip duplicates int left = j + 1; int right = numsSize - 1; while (left < right) { long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { printf("%d -> %d -> %d -> %d -> null\n", nums[i], nums[j], nums[left], nums[right]); // skip duplicates 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--; } } } } } int main() { int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0; int size = sizeof(nums) / sizeof(nums[0]); fourSum(nums, size, target); return 0; }

Result

Printed unique quadruplets that sum to target, e.g.: -2 -> -1 -> 1 -> 2 -> null -2 -> 0 -> 0 -> 2 -> null -1 -> 0 -> 0 -> 1 -> null

Seeing the full code connects all concepts and shows how to implement the solution efficiently.

7

Expert

Handling Large Inputs and Integer Overflow

🤔Before reading on: Do you think adding four integers can overflow int type? Commit to your answer.

Concept: Use wider integer types to avoid overflow and optimize for large inputs.

When adding four integers, the sum might exceed the range of int. Using long long (64-bit) prevents overflow. Also, sorting and skipping duplicates reduces time complexity from O(n^4) to O(n^3). For very large inputs, further optimizations or parallel processing might be needed.

Result

Robust solution that works correctly on large or extreme inputs.

Understanding data type limits and complexity helps build reliable and scalable solutions.

Under the Hood

The algorithm sorts the array first, then uses nested loops to fix two numbers. For the remaining two numbers, it uses two pointers moving inward to find pairs that sum to the required value. Skipping duplicates ensures unique quadruplets. Sorting allows efficient pair searching and duplicate detection.

Why designed this way?

Sorting and two-pointer technique reduce the brute force O(n^4) search to O(n^3), making the problem solvable for larger inputs. Skipping duplicates avoids repeated results without extra memory. Alternatives like hash maps exist but can be more complex or use more space.

Input array
  ↓ sort
Sorted array: ┌─────────────────────────────┐
               │ a1, a2, a3, ..., an        │
               └─────────────────────────────┘
Fix i and j:   ┌─────┐
               │ i,j │
               └─────┘
Two pointers:  left ->           ← right
               ┌─────────────────────────────┐
               │ a[left], ..., a[right]       │
               └─────────────────────────────┘
Sum check -> move pointers or record quadruplet
Skip duplicates -> continue loops
Output unique quadruplets

Myth Busters - 4 Common Misconceptions

Quick: Does sorting the array change the quadruplets we find? Commit yes or no.

Common Belief: Sorting changes the order and might lose some quadruplets.

Reality: Sorting only rearranges numbers but does not remove any. All quadruplets still exist, just in sorted order.

Why it matters: Believing sorting loses solutions might prevent using efficient methods, leading to slower, more complex code.

Quick: Can we find quadruplets by checking all combinations without sorting? Commit yes or no.

Common Belief: Brute force without sorting is fine and simple enough.

Reality: Brute force is correct but very slow (O(n^4)) and impractical for large inputs.

Why it matters: Ignoring sorting and two-pointer techniques leads to inefficient solutions that don't scale.

Quick: If we find one quadruplet, can we skip checking others with the same numbers? Commit yes or no.

Common Belief: No need to skip duplicates; all quadruplets are valid.

Reality: Skipping duplicates is necessary to avoid repeated quadruplets in output.

Why it matters: Not skipping duplicates causes redundant output and confusion.

Quick: Can integer overflow happen when adding four numbers? Commit yes or no.

Common Belief: Integer overflow is not a concern for this problem.

Reality: Sum of four integers can overflow int type; using larger types like long long is safer.

Why it matters: Ignoring overflow can cause wrong results or crashes in real applications.

Expert Zone

1

The order of skipping duplicates matters: skipping too early or late can miss valid quadruplets or cause duplicates.

2

Using long long for sum prevents subtle bugs in edge cases with large positive or negative numbers.

3

The two-pointer approach relies on sorted data; any unsorted input breaks the logic and correctness.

When NOT to use

This approach is less effective if the input is huge and unsorted with many duplicates; hashing-based methods or approximate algorithms might be better. For k-sum with k > 4, recursive or more advanced pruning techniques are preferred.

Production Patterns

Used in recommendation systems to find combinations of features matching criteria, in finance to detect sets of transactions summing to suspicious amounts, and in coding interviews to test problem-solving and optimization skills.

Connections

Two Sum Problem

Builds-on

Understanding two sum with two pointers is the foundation for solving four sum by fixing two numbers and searching pairs.

Combination Sum in Mathematics

Same pattern

Both problems involve finding number combinations that sum to a target, linking algorithmic search to combinatorial math.

Team Formation in Human Resources

Analogous problem

Selecting unique groups of people meeting criteria mirrors finding unique quadruplets, showing how algorithms model real-world grouping challenges.

Common Pitfalls

#1 Not sorting the array before searching.

Wrong approach:

for (i=0; i

Correct approach:

qsort(nums, n, sizeof(int), cmpfunc);
// then use two-pointer method with skipping duplicates

Root cause:

Without sorting, two-pointer technique and duplicate skipping cannot be applied.

#2 Not skipping duplicates leads to repeated quadruplets.

Wrong approach:

if (sum == target) {
print quadruplet;
left++;
right--;
}

Correct approach:

if (sum == target) {
print quadruplet;
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}

Root cause:

Failing to skip duplicates causes multiple identical quadruplets to be printed.

#3 Using int type for sum causing overflow.

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:

Int type may overflow if numbers are large, causing incorrect comparisons.

Key Takeaways

Sorting the array is essential to efficiently find quadruplets and avoid duplicates.

Fixing two numbers and using two pointers for the other two reduces complexity from O(n^4) to O(n^3).

Skipping duplicates at every step ensures unique quadruplets without extra memory.

Using a wider integer type prevents overflow when summing multiple numbers.

This problem builds on simpler sum problems and teaches techniques useful in many combination search tasks.