Four Sum Problem All Unique Quadruplets in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum Quadruplets for a Given Array and Target

What is the output of the following C++ code that finds all unique quadruplets in the array that sum to the target 0?

DSA C++

std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n - 3; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        for (int j = i + 1; j < n - 2; ++j) {
            if (j > i + 1 && nums[j] == nums[j-1]) continue;
            int left = j + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({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;
                }
            }
        }
    }
    return result;
}

int main() {
    std::vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    auto res = fourSum(nums, target);
    for (auto &quad : res) {
        for (int num : quad) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

A

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

B

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

C

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

D

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

💡 Hint

Think about sorting the array and using two pointers to find pairs that complete the quadruplet.

The code sorts the array and uses two nested loops with two pointers to find quadruplets that sum to the target. It skips duplicates to ensure unique quadruplets. The correct output matches option A.

🧠 Conceptual

intermediate

Number of Unique Quadruplets for Four Sum

Given the array nums = [2, 2, 2, 2, 2] and target = 8, how many unique quadruplets does the Four Sum algorithm find?

A 10

B 5

C 0

D 1

💡 Hint

All elements are the same, so only one unique quadruplet can sum to 8.

Since all elements are 2, the only quadruplet summing to 8 is [2, 2, 2, 2]. The algorithm skips duplicates, so only one unique quadruplet is found.

🔧 Debug

advanced

Identify the Bug in Four Sum Implementation

What error will the following code produce when run, and why?

DSA C++

std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n - 3; ++i) {
        for (int j = i + 1; j < n - 2; ++j) {
            int left = j + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                    ++left; --right;
                } else if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
    }
    return result;
}

A Runtime error due to out-of-bounds access

B Compilation error due to missing semicolon

C No error, but duplicates quadruplets will be included

D Infinite loop because left and right pointers never move

💡 Hint

Check if the code handles duplicate quadruplets properly.

The code does not skip duplicate values for i, j, left, or right indices, so it will include duplicate quadruplets but will not cause runtime or compilation errors.

❓ Predict Output

advanced

Output of Four Sum with Negative Target

What is the output of the following code snippet for nums = [-3, -1, 0, 2, 4, 5] and target = 2?

DSA C++

std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n - 3; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        for (int j = i + 1; j < n - 2; ++j) {
            if (j > i + 1 && nums[j] == nums[j-1]) continue;
            int left = j + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({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;
                }
            }
        }
    }
    return result;
}

int main() {
    std::vector<int> nums = {-3, -1, 0, 2, 4, 5};
    int target = 2;
    auto res = fourSum(nums, target);
    for (auto &quad : res) {
        for (int num : quad) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

A

[-3 -1 0 5]
[-3 0 2 3]

B [-3 -1 2 4]

C [-3 -1 0 5]

D

[-3 -1 2 4]
[-3 0 2 3]

💡 Hint

Check sums of quadruplets carefully after sorting.

Only one quadruplet sums to 2: [-3, -1, 2, 4]. Other options include numbers not in the array or sums that don't match target.

🚀 Application

expert

Minimum Number of Quadruplets to Cover All Elements

Given an array nums = [1, 0, -1, 0, -2, 2], what is the minimum number of unique quadruplets from the Four Sum problem with target 0 needed to cover all elements in the array at least once?

A 2

B 1

C 3

D 4

💡 Hint

Find quadruplets that cover all elements with minimal overlap.

The unique quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1]. To cover all elements (1,0,-1,0,-2,2), at least two quadruplets are needed.

Practice

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

easy

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

B. Sort the array in ascending order

C. Find the maximum element in the array

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 all unique sets of four numbers in an array that add up to a specific target sum.

2. Step 2: Identify the goal

   The goal is to find quadruplets (groups of four numbers) that sum exactly to the target, without duplicates.

3. Final Answer:

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

4. Quick Check:

   Four Sum Problem = Find quadruplets summing to target [OK]

Hint: Look for four numbers adding to target without repeats [OK]

Common Mistakes:

• Confusing with pair or triplet sum problems
• Ignoring uniqueness of quadruplets
• Trying to sort only without finding quadruplets

2. Which of the following C++ code snippets correctly initializes a vector to store quadruplets for the Four Sum Problem?

easy

A. std::vector<int> quadruplets(4);

B. std::vector quadruplets;

C. std::vector<int> quadruplets = {4};

D. std::vector> quadruplets;

Solution

1. Step 1: Understand the data structure needed

   We need to store multiple quadruplets, each is a vector of 4 integers, so a vector of vector<int> is suitable.

2. Step 2: Check each option

   std::vector quadruplets; declares a vector of vector<int>, perfect for storing multiple quadruplets. std::vector<int> quadruplets(4); creates a single vector of size 4, not multiple quadruplets. std::vector<int> quadruplets = {4}; initializes a vector with one element 4, incorrect. std::vector> quadruplets; uses pairs, which store only two integers, not four.

3. Final Answer:

   std::vector quadruplets; -> Option B

4. Quick Check:

   Use vector of vector<int> for quadruplets [OK]

Hint: Use vector of vector<int> to store multiple quadruplets [OK]

Common Mistakes:

• Using vector<int> for multiple quadruplets
• Using pairs instead of quadruplets
• Initializing vector with wrong size or values

3. What will be the output of the following C++ code snippet for input array {1, 0, -1, 0, -2, 2} and target 0?

std::vector<int> nums = {1, 0, -1, 0, -2, 2};
int target = 0;
// Assume fourSum function returns all unique quadruplets
auto result = fourSum(nums, target);
for (auto &quad : result) {
    for (int num : quad) std::cout << num << " ";
    std::cout << std::endl;
}

medium

A. [-2 -1 1 2]
[-2 0 0 2]
[-1 0 0 1]

B. [-2 -1 0 1]
[-1 0 0 2]

C. [-2 -2 1 3]
[-1 0 0 1]

D. No quadruplets found

Solution

1. Step 1: Sort the array and find quadruplets summing to target 0

   Sorted array: [-2, -1, 0, 0, 1, 2]. The unique quadruplets summing to 0 are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

2. Step 2: Verify output matches quadruplets

   [-2 -1 1 2] [-2 0 0 2] [-1 0 0 1] lists exactly these three quadruplets. Options A, C, and D have incorrect quadruplets or sums.

3. Final Answer:

   [-2 -1 1 2] [-2 0 0 2] [-1 0 0 1] -> Option A

4. Quick Check:

   Unique quadruplets summing to 0 = [-2 -1 1 2] [-2 0 0 2] [-1 0 0 1] [OK]

Hint: Sort array first, then find quadruplets summing to target [OK]

Common Mistakes:

• Not sorting array before searching
• Including duplicate quadruplets
• Missing some valid quadruplets

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

std::vector fourSum(std::vector<int>& nums, int target) {
    std::vector result;
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size(); ++j) {
            int left = j + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                    ++left; --right;
                } else if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
    }
    return result;
}

medium

A. Returns result before completing loops

B. Incorrect sorting of the input array

C. Wrong initialization of left and right pointers

D. Does not skip duplicate quadruplets, causing repeated results

Solution

1. Step 1: Analyze duplicate handling in loops

   The code does not skip duplicates for i, j, left, or right indices, so it can add the same quadruplet multiple times.

2. Step 2: Check other parts for errors

   Sorting is correct, left and right pointers are initialized properly, and return is after loops. So these are not bugs.

3. Final Answer:

   Does not skip duplicate quadruplets, causing repeated results -> Option D

4. Quick Check:

   Missing duplicate checks = Does not skip duplicate quadruplets, causing repeated results [OK]

Hint: Always skip duplicates after finding quadruplets [OK]

Common Mistakes:

• Not skipping duplicates for i, j, left, right
• Returning result too early
• Incorrect pointer initialization

5. Given an array nums = {2, 2, 2, 2, 2} and target 8, how many unique quadruplets does the Four Sum algorithm find, and what are they?

hard

A. 10 quadruplets: including duplicates

B. 5 quadruplets: all combinations of 2s

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

D. 0 quadruplets: no quadruplets sum to 8

Solution

1. Step 1: Understand the input and target

   All elements are 2, and target is 8. Sum of four 2s is 8, so quadruplet [2, 2, 2, 2] is valid.

2. Step 2: Consider uniqueness

   Even though multiple combinations exist, they are duplicates. The algorithm returns only one unique quadruplet.

3. Final Answer:

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

4. Quick Check:

   All 2s sum to 8 once uniquely [OK]

Hint: Duplicates count as one unique quadruplet [OK]

Common Mistakes:

• Counting duplicate quadruplets multiple times
• Assuming no quadruplets because of repeated numbers
• Confusing number of combinations with unique quadruplets