Four Sum Problem All Unique Quadruplets in DSA C++ - Execution Trace

Concept Flow - Four Sum Problem All Unique Quadruplets

Start with sorted array

↓

Fix first element i

↓

Fix second element j > i

↓

Use two pointers: left = j+1, right = end

↓

Check sum of nums[i

↓

Repeat until left >= right

↓

Move j skipping duplicates

↓

Move i skipping duplicates

↓

Done: return all unique quadruplets

We fix two elements and use two pointers to find pairs that sum to the target minus the fixed elements, skipping duplicates to get unique quadruplets.

Execution Sample

DSA C++

nums = [1, 0, -1, 0, -2, 2]
target = 0
Sort nums
for i in range(len(nums)-3):
  for j in range(i+1, len(nums)-2):
    left, right = j+1, len(nums)-1
    while left < right:
      sum = nums[i]+nums[j]+nums[left]+nums[right]
      if sum == target: store quadruplet
      adjust pointers skipping duplicates

Find all unique quadruplets in nums that sum to target by fixing two elements and using two pointers for the other two.

Execution Table

Step	Operation	i,j,left,right	Sum	Action	Quadruplets Found	Visual State (Sorted Array)
1	Sort array	-	-	-	Array sorted	[-2, -1, 0, 0, 1, 2]
2	Fix i=0	i=0	-	-	-	i points to -2
3	Fix j=1	i=0, j=1	-	-	-	j points to -1
4	Set left=2, right=5	i=0, j=1, left=2, right=5	-	-	-	left=0, right=2
5	Calculate sum	i=0, j=1, left=2, right=5	-2 + -1 + 0 + 2 = -1	Sum < target, move left++	[]	Array unchanged
6	Move left to 3	i=0, j=1, left=3, right=5	-	-	-	left=0 (index 3)
7	Calculate sum	i=0, j=1, left=3, right=5	-2 + -1 + 0 + 2 = -1	Sum < target, move left++	[]	Array unchanged
8	Move left to 4	i=0, j=1, left=4, right=5	-	-	-	left=1 (index 4)
9	Calculate sum	i=0, j=1, left=4, right=5	-2 + -1 + 1 + 2 = 0	Sum == target, store quadruplet	[[-2, -1, 1, 2]]	Array unchanged
10	Move left++ and right-- skipping duplicates	i=0, j=1, left=5, right=4	-	-	-	left > right, end while
11	Increment j to 2	i=0, j=2	-	-	-	j points to 0
12	Set left=3, right=5	i=0, j=2, left=3, right=5	-	-	-	left=0 (index 3), right=2
13	Calculate sum	i=0, j=2, left=3, right=5	-2 + 0 + 0 + 2 = 0	Sum == target, store quadruplet	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	Array unchanged
14	Move left++ and right-- skipping duplicates	i=0, j=2, left=4, right=4	-	-	-	left >= right, end while
15	Increment j to 3	i=0, j=3	-	-	-	j points to 0 (duplicate), skip to next
16	Increment i to 1	i=1	-	-	-	i points to -1
17	Fix j=2	i=1, j=2	-	-	-	j points to 0
18	Set left=3, right=5	i=1, j=2, left=3, right=5	-	-	-	left=0 (index 3), right=2
19	Calculate sum	i=1, j=2, left=3, right=5	-1 + 0 + 0 + 2 = 1	Sum > target, move right--	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	Array unchanged
20	Move right to 4	i=1, j=2, left=3, right=4	-	-	-	right=1 (index 4)
21	Calculate sum	i=1, j=2, left=3, right=4	-1 + 0 + 0 + 1 = 0	Sum == target, store quadruplet	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	Array unchanged
22	Move left++ and right-- skipping duplicates	i=1, j=2, left=4, right=3	-	-	-	left >= right, end while
23	Increment j to 3	i=1, j=3	-	-	-	j points to 0 (duplicate), skip
24	Increment i to 2	i=2	-	-	-	i points to 0
25	Fix j=3	i=2, j=3	-	-	-	j points to 0 (duplicate), skip
26	Increment i to 3	i=3	-	-	-	i points to 0 (duplicate), skip
27	End loop	-	-	-	-	All quadruplets found
28	Return result	-	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	Final quadruplets

💡 i reaches len(nums)-3, no more quadruplets possible

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 9	After Step 13	After Step 21	Final
i	-	0	0	0	0	0	1	1
j	-	-	1	1	1	2	2	2
left	-	-	-	2	4	3	3	-
right	-	-	-	5	5	5	4	-
Quadruplets	[]	[]	[]	[]	[[-2,-1,1,2]]	[[-2,-1,1,2],[-2,0,0,2]]	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]	[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Key Moments - 3 Insights

Why do we skip duplicates for i, j, left, and right pointers?

Skipping duplicates prevents adding the same quadruplet multiple times. For example, after finding a quadruplet, we move left and right pointers past duplicates (see steps 9 and 13) to avoid repeated quadruplets.

Why do we move left pointer when sum < target and right pointer when sum > target?

Because the array is sorted, increasing left moves to a bigger number increasing sum, and decreasing right moves to a smaller number decreasing sum. This helps find the target sum efficiently (see steps 5-8 and 19-20).

Why do we stop the while loop when left >= right?

When left meets or passes right, all pairs between j and end are checked for current i and j. No more pairs remain to check (see step 10 and 14).

Visual Quiz - 3 Questions

Look at the execution table at step 9. What quadruplet was found?

A [-2, -1, 1, 2]

B [-2, 0, 0, 2]

C [-1, 0, 0, 1]

D [0, 0, 1, 2]

💡 Hint

Check the 'Quadruplets Found' column at step 9 in the execution_table.

At which step does the left pointer move past duplicates after finding a quadruplet?

A Step 5

B Step 10

C Step 13

D Step 19

💡 Hint

Look for the step after storing quadruplet where left and right pointers move skipping duplicates.

If the array was not sorted, which part of the execution would fail?

A Fixing i and j elements

B Skipping duplicates

C Using two pointers left and right to find pairs

D Storing quadruplets

💡 Hint

Two pointers rely on sorted order to move left/right correctly (see concept_flow).

Concept Snapshot

Four Sum Problem:
- Sort array first
- Fix two indices i, j
- Use two pointers left, right to find pairs
- Move pointers based on sum vs target
- Skip duplicates for unique quadruplets
- Return all quadruplets found

Full Transcript

The Four Sum problem finds all unique quadruplets in an array that sum to a target. We first sort the array to use two pointers efficiently. We fix two elements i and j, then use two pointers left and right to find pairs that complete the quadruplet. We calculate the sum of these four elements. If the sum equals the target, we store the quadruplet and move pointers skipping duplicates to avoid repeats. If the sum is less than the target, we move left pointer forward to increase sum. If the sum is greater, we move right pointer backward to decrease sum. We repeat until left meets right, then move j and i skipping duplicates. This process continues until all quadruplets are found. The key is sorting and skipping duplicates to ensure uniqueness and efficiency.

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