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.