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.

Practice

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

easy

A. Find the maximum element in the array

B. Sort the array in ascending order

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

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 four numbers in an array whose sum equals a target value.

2. Step 2: Identify the expected output

   We want all unique sets of four numbers (quadruplets) that add up to the target.

3. Final Answer:

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

4. Quick Check:

   Four Sum = unique quadruplets with target sum [OK]

Hint: Look for four numbers adding to target, not just pairs [OK]

Common Mistakes:

• Confusing with two or three sum problems
• Ignoring uniqueness of quadruplets
• Trying to find maximum or minimum instead of sum

2. Which of the following code snippets correctly initializes the array and target for the Four Sum problem in C?

easy

A. int nums[] = [1, 0, -1, 0, -2, 2]; int target = 0;

B. int nums = {1, 0, -1, 0, -2, 2}; int target = 0;

C. int nums[] = (1, 0, -1, 0, -2, 2); int target = 0;

D. int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0;

Solution

1. Step 1: Check array initialization syntax in C

   Arrays in C are initialized with curly braces {} and square brackets [] for declaration.

2. Step 2: Validate each option

   int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0; uses correct syntax: int nums[] = { ... }; int nums = {1, 0, -1, 0, -2, 2}; int target = 0; misses brackets, C uses parentheses, D uses square brackets incorrectly.

3. Final Answer:

   int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0; -> Option D

4. Quick Check:

   Correct C array syntax = int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0; [OK]

Hint: Use curly braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Missing square brackets [] in declaration
• Using square brackets [] for initialization

3. Given the following C code snippet, what will be the printed output for the quadruplets found?

int nums[] = {1, 0, -1, 0, -2, 2};
int target = 0;
// Assume function fourSum returns all unique quadruplets
// and prints them as quadruplets separated by spaces
// Output format: a b c d\n for each quadruplet
fourSum(nums, 6, target);

medium

A. 1 0 -1 0
-2 2 0 0
-1 1 0 0

B. -2 -1 1 2
-2 0 0 2
-1 0 0 1

C. -2 -1 0 1
-2 0 0 2
-1 0 1 2

D. No quadruplets found

Solution

1. Step 1: Sort the array

   Sorted nums = [-2, -1, 0, 0, 1, 2]

2. Step 2: Find all unique quadruplets summing to 0

   Quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

3. Final Answer:

   -2 -1 1 2 -2 0 0 2 -1 0 0 1 -> Option B

4. Quick Check:

   Sum of each quadruplet = 0 [OK]

Hint: Sort array first, then use two pointers for pairs [OK]

Common Mistakes:

• Not sorting array before processing
• Including duplicate quadruplets
• Incorrect sum calculation

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

void fourSum(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize - 3; i++) {
        for (int j = i + 1; j < numsSize - 2; j++) {
            int left = j + 1, right = numsSize - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    printf("%d %d %d %d\n", nums[i], nums[j], nums[left], nums[right]);
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
}

medium

A. No check to skip duplicate quadruplets causing repeated outputs

B. Incorrect initialization of left and right pointers

C. Wrong loop ranges causing out-of-bounds access

D. Missing return statement in void function

Solution

1. Step 1: Analyze duplicate handling

   The code prints quadruplets but does not skip duplicates, so repeated quadruplets appear.

2. Step 2: Check other parts

   Left and right pointers are correctly initialized; loop ranges are valid; return statement is not needed in void function.

3. Final Answer:

   No check to skip duplicate quadruplets causing repeated outputs -> Option A

4. Quick Check:

   Duplicates not skipped = No check to skip duplicate quadruplets causing repeated outputs [OK]

Hint: Skip duplicates after finding quadruplets to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates for i, j, left, right
• Incorrect pointer updates causing infinite loops
• Accessing array out of bounds

5. You are given an array nums = {2, 2, 2, 2, 2} and target 8. How many unique quadruplets sum to the target, and what are they?

hard

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

B. 5 quadruplets: all combinations of 2's

C. 0 quadruplets: no unique quadruplets

D. 4 quadruplets: different indices but same values

Solution

1. Step 1: Understand array and target

   All elements are 2, target is 8, so quadruplet sum must be 2+2+2+2=8.

2. Step 2: Count unique quadruplets

   Even though multiple indices exist, the quadruplet values are the same, so only one unique quadruplet exists: [2, 2, 2, 2].

3. Final Answer:

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

4. Quick Check:

   Sum 2+2+2+2=8 unique quadruplet [OK]

Hint: Same values quadruplet counts as one unique quadruplet [OK]

Common Mistakes:

• Counting quadruplets by indices, not unique values
• Assuming multiple quadruplets due to duplicates
• Ignoring uniqueness condition