Four Sum Problem All Unique Quadruplets in DSA C - Build from Scratch

Four Sum Problem All Unique Quadruplets

📖 Scenario: You are working on a shopping app that needs to find all unique sets of four product prices that add up to a customer's gift card value.This helps customers find combinations of products they can buy exactly with their gift card.

🎯 Goal: Build a program that finds all unique quadruplets in an array of integers that sum up to a target value.This will help the app suggest product combinations matching the gift card amount.

📋 What You'll Learn

Create an integer array called nums with the exact values: {1, 0, -1, 0, -2, 2}

Create an integer variable called target and set it to 0

Write a function called fourSum that takes nums, its size, target, and prints all unique quadruplets that sum to target

Use sorting and two-pointer technique inside fourSum to find quadruplets efficiently

Print each quadruplet in the format: [a, b, c, d] on its own line

💡 Why This Matters

🌍 Real World

Finding combinations of product prices that match a gift card value helps customers shop efficiently and improves user experience in e-commerce apps.

💼 Career

This problem teaches array manipulation, sorting, and two-pointer techniques which are common in coding interviews and real-world software development.

1

Create the input array

Create an integer array called nums with the exact values {1, 0, -1, 0, -2, 2} and an integer variable n that stores the size of nums.

DSA C

int nums[] = {1, 0, -1, 0, -2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
// Your code here

Hint

Use int nums[] = {1, 0, -1, 0, -2, 2}; to create the array and calculate size with sizeof(nums) / sizeof(nums[0]).

2

Set the target sum

Create an integer variable called target and set it to 0.

DSA C

int nums[] = {1, 0, -1, 0, -2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
int target = 0;
// Your code here

Hint

Simply write int target = 0; to set the target sum.

3

Write the fourSum function

Write a function called fourSum that takes int* nums, int n, and int target. Inside, sort nums using qsort. Then use nested loops and two pointers to find all unique quadruplets that sum to target. Print each quadruplet in the format [a, b, c, d] on its own line.

DSA C

int nums[] = {1, 0, -1, 0, -2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
int target = 0;

// Write the fourSum function here
// Your code here

Hint

Use qsort to sort the array. Use two nested loops for the first two numbers, then two pointers left and right to find pairs that complete the quadruplet.

4

Call fourSum and print results

Call the fourSum function with nums, n, and target to print all unique quadruplets.

DSA C

#include 
#include 

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

void fourSum(int* nums, int n, int target) {
    qsort(nums, n, sizeof(int), compare);
    for (int i = 0; i  0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j  i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1;
            int right = n - 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]);
                    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 n = sizeof(nums) / sizeof(nums[0]);
    int target = 0;
    // Call fourSum here
    // Your code here
    return 0;
}

Hint

Call fourSum(nums, n, target); inside main to print the quadruplets.

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