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 picking four friends from a group so their combined ages equal a special number, but you never pick the same group twice even if ages repeat.

Array: [1, 0, -1, 0, -2, 2]
Indexes:  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 avoid duplicates and use two pointers

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

Why: Sorting helps us skip duplicates and use two pointers efficiently

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

[-2, -1, 0, 0, 1, 2]
First = -2, Second = -1

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

Step 3: Use two pointers: left at index 2 (0), right at index 5 (2), sum = -2 + -1 + 0 + 2 = -1

[-2, -1, 0, 0, 1, 2]
Pointers: left=2, right=5, sum=-1

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

Step 4: Move left pointer to index 3 (0), sum = -2 + -1 + 0 + 2 = -1 again

[-2, -1, 0, 0, 1, 2]
Pointers: left=3, right=5, sum=-1

Why: Still less than target, move left pointer again

Step 5: Move left pointer to index 4 (1), sum = -2 + -1 + 1 + 2 = 0, quadruplet found

[-2, -1, 0, 0, 1, 2]
Quadruplet: [-2, -1, 1, 2]

Why: Sum equals target, record quadruplet and move pointers to find others

Step 6: Fix first number at index 0 (-2), second number at index 2 (0), use two pointers left=3 (0), right=5 (2)

[-2, -1, 0, 0, 1, 2]
First=-2, Second=0, left=3, right=5

Why: Try new second number to find other quadruplets

Step 7: Sum = -2 + 0 + 0 + 2 = 0, quadruplet found

[-2, -1, 0, 0, 1, 2]
Quadruplet: [-2, 0, 0, 2]

Why: Sum equals target, record quadruplet

Step 8: Fix first number at index 1 (-1), second number at index 2 (0), left=3 (0), right=4 (1)

[-2, -1, 0, 0, 1, 2]
First=-1, Second=0, left=3, right=4

Why: Try new first number to find other quadruplets

Step 9: Sum = -1 + 0 + 0 + 1 = 0, quadruplet found

[-2, -1, 0, 0, 1, 2]
Quadruplet: [-1, 0, 0, 1]

Why: Sum equals target, record quadruplet

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Structure to hold quadruplets
typedef struct {
    int nums[4];
} Quadruplet;

// Dynamic array to hold results
typedef struct {
    Quadruplet* data;
    int size;
    int capacity;
} Result;

void addQuadruplet(Result* res, int a, int b, int c, int d) {
    // Resize if needed
    if (res->size == res->capacity) {
        res->capacity = res->capacity == 0 ? 4 : res->capacity * 2;
        res->data = realloc(res->data, res->capacity * sizeof(Quadruplet));
    }
    res->data[res->size].nums[0] = a;
    res->data[res->size].nums[1] = b;
    res->data[res->size].nums[2] = c;
    res->data[res->size].nums[3] = d;
    res->size++;
}

int cmpfunc(const void* a, const void* b) {
    int x = *(int*)a;
    int y = *(int*)b;
    return x - y;
}

void fourSum(int* nums, int numsSize, int target, Result* res) {
    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 i
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates for j
            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) {
                    addQuadruplet(res, 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++;
                } else {
                    right--;
                }
            }
        }
    }
}

int main() {
    int nums[] = {1, 0, -1, 0, -2, 2};
    int target = 0;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    Result res = {NULL, 0, 0};

    fourSum(nums, numsSize, target, &res);

    for (int i = 0; i < res.size; i++) {
        printf("[%d, %d, %d, %d]\n", res.data[i].nums[0], res.data[i].nums[1], res.data[i].nums[2], res.data[i].nums[3]);
    }

    free(res.data);
    return 0;
}

qsort(nums, numsSize, sizeof(int), cmpfunc);

Sort array to enable two-pointer technique and skip duplicates

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 sum

if (sum == target) { addQuadruplet(...); skip duplicates; left++; right--; }

When sum matches target, record quadruplet and move pointers skipping duplicates

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

Adjust pointers to increase or decrease sum towards target

Output

[-2, -1, 1, 2]

[-2, 0, 0, 2]

[-1, 0, 0, 1]

Complexity Analysis

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

Space: O(k) where k is number of quadruplets found, plus O(n) for sorting

vs Alternative: Naive approach is O(n^4) checking all quadruplets; this method is faster by sorting and two pointers

Edge Cases

Empty array

No quadruplets found, function returns immediately

DSA C

if (numsSize < 4) return;

Array with less than 4 elements

No quadruplets possible, function returns immediately

DSA C

if (numsSize < 4) return;

All elements are the same and sum matches target

Only one quadruplet recorded, duplicates skipped

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 skipping duplicates for i, j, left, or right pointers causing repeated quadruplets
Fix: Add checks to skip duplicates after sorting for all four positions

Mistake: Using int sum causing overflow on large inputs
Fix: Use long long for sum calculation to avoid overflow

Summary

Find all unique groups of four numbers that add up to a target sum.

Use when you need to find quadruplets in an array that sum to a specific value without repeats.

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