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 whose combined ages add up to a birthday milestone, making sure you don't count the same group twice even if friends have the same age.

Array: [1, 0, -1, 0, -2, 2]
Indices:  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 quadruplets that sum to 0

Step 1: Sort the array to [-2, -1, 0, 0, 1, 2]

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

Why: Sorting helps to avoid duplicates and use two pointers efficiently

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

[-2, -1, 0, 0, 1, 2]
Indices: 0  1  [2]       [5]

Why: We try to find two numbers between left and right that sum with fixed numbers to target

Step 3: Calculate sum: -2 + -1 + 0 + 2 = -1, less than target, move left pointer right

[-2, -1, 0, 0, 1, 2]
Indices: 0  1     [3]    [5]

Why: Sum too small, increase sum by moving left pointer right

Step 4: Calculate sum: -2 + -1 + 0 + 2 = -1 again, move left pointer right

[-2, -1, 0, 0, 1, 2]
Indices: 0  1        [4] [5]

Why: Sum still less than target, move left pointer right

Step 5: Calculate sum: -2 + -1 + 1 + 2 = 0, quadruplet found [-2, -1, 1, 2]

Quadruplets: [[-2, -1, 1, 2]]

Why: Sum matches target, add quadruplet and move both pointers to avoid duplicates

Step 6: Move second number to index 2 (0), left=3, right=5

[-2, -1, 0, 0, 1, 2]
Indices: 0  [2] [3]    [5]

Why: Try new second number to find other quadruplets

Step 7: Calculate sum: -2 + 0 + 0 + 2 = 0, quadruplet found [-2, 0, 0, 2]

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

Why: Sum matches target, add quadruplet and move pointers

Step 8: Move first number to index 1 (-1), second number to index 2 (0), left=3, right=5

[-2, -1, 0, 0, 1, 2]
Indices: [1] [2] [3]    [5]

Why: Try new first and second numbers to find more quadruplets

Step 9: Calculate sum: -1 + 0 + 0 + 2 = 1, greater than target, move right pointer left

Indices: [1] [2] [3]    [4]

Why: Sum too big, decrease sum by moving right pointer left

Step 10: Calculate sum: -1 + 0 + 0 + 1 = 0, quadruplet found [-1, 0, 0, 1]

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

Why: Sum matches target, add quadruplet and move pointers

Result:

Quadruplets: [-2, -1, 1, 2] -> [-2, 0, 0, 2] -> [-1, 0, 0, 1]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class FourSumSolution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums); // sort array to use two pointers and avoid duplicates
        List<IList<int>> result = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for first number
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates for second number
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.Add(new List<int>{nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++; // skip duplicates
                        while (left < right && nums[right] == nums[right + 1]) right--; // skip duplicates
                    } else if (sum < target) {
                        left++; // increase sum
                    } else {
                        right--; // decrease sum
                    }
                }
            }
        }
        return result;
    }

    static void Main() {
        FourSumSolution sol = new FourSumSolution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        var quadruplets = sol.FourSum(nums, target);
        foreach (var quad in quadruplets) {
            Console.WriteLine(string.Join(", ", quad));
        }
    }
}

Array.Sort(nums); // sort array to use two pointers and avoid duplicates

sort array to enable two-pointer technique and skip duplicates

if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates for first number

skip repeated first numbers to avoid duplicate quadruplets

if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates for second number

skip repeated second numbers to avoid duplicate quadruplets

while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; ... }

use two pointers to find pairs that complete quadruplet sum

if (sum == target) { result.Add(...); left++; right--; while (...) left++; while (...) right--; }

found quadruplet, add to result and move pointers skipping duplicates

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

adjust pointers to increase or decrease sum

Output

-2, -1, 1, 2

-2, 0, 0, 2

-1, 0, 0, 1

Complexity Analysis

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

Space: O(k) where k is number of quadruplets found, for storing results

vs Alternative: Better than naive O(n^4) which tries all quadruplets; sorting and two pointers reduce complexity

Edge Cases

Empty array

Returns empty list, no quadruplets found

DSA C#

for (int i = 0; i < n - 3; i++) { ... } handles arrays with less than 4 elements by not entering loop

Array with less than 4 elements

No quadruplets possible, returns empty list

DSA C#

for (int i = 0; i < n - 3; i++) { ... } prevents processing

All elements same and sum matches target

Returns one quadruplet with those elements, duplicates skipped

DSA C#

if (i > 0 && nums[i] == nums[i - 1]) continue; and similar for j and pointers

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 sorting the array before processing
Fix: Sort the array first to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for i, j, left, or right pointers
Fix: Add checks to skip repeated values to avoid duplicate quadruplets

Mistake: Moving pointers incorrectly after finding a quadruplet
Fix: After adding quadruplet, move both pointers and skip duplicates carefully

Summary

Finds 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 and skip duplicates.

Practice

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

easy

A. Sort the array in ascending order

B. Count the number of pairs with a given sum

C. Find the maximum element in the array

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

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: Differentiate from other problems

   Unlike sorting or finding maximum, this problem focuses on quadruplets and their sums, not individual elements or pairs.

3. Final Answer:

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

4. Quick Check:

   Four Sum Problem = Find quadruplets with target sum [OK]

Hint: Look for four numbers adding to target, not sorting or max [OK]

Common Mistakes:

• Confusing with sorting or max element problems
• Looking for pairs instead of quadruplets
• Ignoring uniqueness of quadruplets

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

easy

A. var quadruplets = new List<List<int>>();

B. var quadruplets = new List<int>();

C. var quadruplets = new Dictionary<int, int>();

D. var quadruplets = new int[4];

Solution

1. Step 1: Identify the data structure for storing quadruplets

   Each quadruplet is a list of 4 integers, so a list of lists is needed to store multiple quadruplets.

2. Step 2: Match with C# syntax

   Using List<List<int>> correctly represents multiple quadruplets, unlike a single list or dictionary.

3. Final Answer:

   var quadruplets = new List<List<int>>(); -> Option A

4. Quick Check:

   Use List of List for quadruplets [OK]

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

Common Mistakes:

• Using List<int> for multiple quadruplets
• Using Dictionary instead of List
• Using fixed-size array for dynamic quadruplets

3. For the input array nums = [1, 0, -1, 0, -2, 2] and target 0, what does FourSum(nums, 0) return?
Assuming FourSum returns all unique quadruplets that sum to target.

medium

A. []

B. [[1, 0, -1, 0]]

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

D. [[0, 0, 0, 0]]

Solution

1. Step 1: Sort and find quadruplets summing to 0

   Sorting nums gives [-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 uniqueness and completeness

   All quadruplets are unique and sum exactly to 0, matching the expected output.

3. Final Answer:

   [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] -> Option C

4. Quick Check:

   Unique quadruplets sum to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array first, then find quadruplets with two pointers [OK]

Common Mistakes:

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

4. Identify the bug in this C# snippet for the Four Sum Problem:

for (int i = 0; i < nums.Length - 3; i++) {
    for (int j = i + 1; j < nums.Length - 2; j++) {
        int left = j + 1, right = nums.Length - 1;
        while (left < right) {
            int sum = nums[i] + nums[j] + nums[left] + nums[right];
            if (sum == target) {
                result.Add(new List<int> { 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 duplicates in result

B. Incorrect initialization of left and right pointers

C. Wrong loop ranges for i and j causing index out of range

D. Missing sorting of the input array before processing

Solution

1. Step 1: Analyze duplicate handling

   The code adds quadruplets without skipping duplicates, so repeated quadruplets can appear in the result.

2. Step 2: Check other parts

   Left and right pointers are correctly initialized; loop ranges are valid; sorting is assumed done before this snippet.

3. Final Answer:

   No check to skip duplicate quadruplets causing duplicates in result -> Option A

4. Quick Check:

   Missing duplicate skip = No check to skip duplicate quadruplets causing duplicates in result [OK]

Hint: Always skip duplicates after finding quadruplets [OK]

Common Mistakes:

• Not skipping duplicates for i, j, left, right
• Assuming sorting is done inside the loop
• Incorrect pointer updates causing infinite loops

5. Given the array nums = [2, 2, 2, 2, 2] and target 8, what is the correct output of the Four Sum Problem algorithm that finds all unique quadruplets?

medium

A. [[2, 2, 2, 2], [2, 2, 2, 2]]

B. [[2, 2, 2, 2]]

C. []

D. [[2, 2, 2]]

Solution

1. Step 1: Understand the input and target

   All elements are 2, and target is 8, so quadruplets of four 2's sum to 8.

2. Step 2: Identify unique quadruplets

   Only one unique quadruplet [2, 2, 2, 2] exists despite duplicates in input.

3. Final Answer:

   [[2, 2, 2, 2]] -> Option B

4. Quick Check:

   Only one unique quadruplet sums to 8 [OK]

Hint: Duplicates form one unique quadruplet if sum matches target [OK]

Common Mistakes:

• Counting duplicate quadruplets multiple times
• Returning empty list when quadruplet exists
• Returning triplets instead of quadruplets