Why Four Sum Problem All Unique Quadruplets in DSA C?

The Big Idea

What if you could find all groups of four numbers adding to a target without checking every single combination?

The Scenario

Imagine you have a list of numbers and want to find all groups of four numbers that add up to a specific target. Doing this by checking every possible group manually is like trying to find four friends in a huge crowd who together have a certain total height--it's confusing and takes forever.

The Problem

Manually checking every combination means looking at thousands or millions of groups, which is very slow and easy to mess up. You might miss some groups or count the same group more than once, making the process frustrating and error-prone.

The Solution

The Four Sum problem uses smart sorting and two-pointer techniques to quickly find all unique groups of four numbers that add up to the target. This method skips unnecessary checks and avoids duplicates, making the search fast and reliable.

Before vs After

✗ Before

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 (arr[i] + arr[j] + arr[k] + arr[l] == target) {
          // print quadruplet
        }
      }
    }
  }
}

✓ After

qsort(arr, n, sizeof(int), compare);
for (int i = 0; i < n-3; i++) {
  if (i > 0 && arr[i] == arr[i-1]) continue;
  for (int j = i+1; j < n-2; j++) {
    if (j > i+1 && arr[j] == arr[j-1]) continue;
    int left = j+1, right = n-1;
    while (left < right) {
      int sum = arr[i] + arr[j] + arr[left] + arr[right];
      if (sum == target) {
        // print quadruplet
        left++; right--;
        while (left < right && arr[left] == arr[left-1]) left++;
        while (left < right && arr[right] == arr[right+1]) right--;
      } else if (sum < target) left++;
      else right--;
    }
  }
}

What It Enables

This approach lets you quickly find all unique sets of four numbers that add up to a target, even in large lists, without missing or repeating any group.

Real Life Example

Suppose you want to find four products from a store that together cost exactly your gift card amount. Using this method helps you find all possible combinations quickly and without repeats.

Key Takeaways

Manual checking of all quadruplets is slow and error-prone.

Sorting and two-pointer technique speeds up the search and avoids duplicates.

This method efficiently finds all unique quadruplets summing to the target.