Four Sum Problem All Unique Quadruplets in DSA Python

Mental Model

Find four numbers in a list that add up to a target without repeating the same group.

Analogy: Imagine picking four different fruits from a basket so their total weight matches a target weight exactly, without picking the same combination twice.

Array: [1, 0, -1, 0, -2, 2]
Target: 0
We want quadruplets like [-2, -1, 1, 2] that sum to 0.

Dry Run Walkthrough

Input: list: [1, 0, -1, 0, -2, 2], target: 0

Goal: Find all unique sets of four numbers that add up to 0

Step 1: Sort the list to make it easier to find quadruplets

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

Why: Sorting helps skip duplicates and use two pointers efficiently

Step 2: Fix first number at index 0 (-2), then fix second number at index 1 (-1)

First two fixed: [-2, -1], searching pairs in [0, 0, 1, 2]

Why: We try to find two numbers that sum with -2 and -1 to target 0

Step 3: Use two pointers: left at index 2 (0), right at index 5 (2), sum = -2 + -1 + 0 + 2 = -1

Sum -1 < target 0, move left pointer right

Why: Sum too small, need bigger numbers

Step 4: Left pointer moves to index 3 (0), sum = -2 + -1 + 0 + 2 = -1 again

Sum still -1 < 0, move left pointer right

Why: Still too small, try next number

Step 5: Left pointer moves to index 4 (1), sum = -2 + -1 + 1 + 2 = 0

Sum equals target, quadruplet found: [-2, -1, 1, 2]

Why: Found one valid quadruplet

Step 6: Move left pointer right and right pointer left to avoid duplicates

Left at 5, right at 4, pointers crossed, end inner loop

Why: No more pairs for these fixed numbers

Step 7: Fix first number at index 0 (-2), second number at index 2 (0)

Searching pairs in [0, 1, 2]

Why: Try new second number to find other quadruplets

Step 8: Two pointers left=3 (0), right=5 (2), sum = -2 + 0 + 0 + 2 = 0

Quadruplet found: [-2, 0, 0, 2]

Why: Found another valid quadruplet

Step 9: Move pointers to avoid duplicates, then continue searching

Pointers crossed, end inner loop

Why: No more pairs for these fixed numbers

Step 10: Fix first number at index 1 (-1), second number at index 2 (0)

Searching pairs in [0, 1, 2]

Why: Try new first number to find more quadruplets

Step 11: Two pointers left=3 (0), right=5 (2), sum = -1 + 0 + 0 + 2 = 1

Sum 1 > target 0, move right pointer left

Why: Sum too big, try smaller number

Step 12: Right pointer moves to index 4 (1), sum = -1 + 0 + 0 + 1 = 0

Quadruplet found: [-1, 0, 0, 1]

Why: Found another valid quadruplet

Step 13: Move pointers to avoid duplicates, then end inner loop

Pointers crossed, no more pairs

Why: No more pairs for these fixed numbers

Result:

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

Annotated Code

DSA Python

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()  # sort to use two pointers and skip duplicates
        quadruplets = []
        n = len(nums)
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue  # skip duplicate first number
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue  # skip duplicate second number
                left, right = j + 1, n - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1  # skip duplicate third number
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1  # skip duplicate fourth number
                    elif total < target:
                        left += 1  # need bigger sum
                    else:
                        right -= 1  # need smaller sum
        return quadruplets

# Driver code
sol = Solution()
result = sol.fourSum([1, 0, -1, 0, -2, 2], 0)
for quad in result:
    print(quad)

nums.sort() # sort to use two pointers and skip duplicates

sort array to enable two-pointer technique and duplicate skipping

if i > 0 and nums[i] == nums[i - 1]: continue # skip duplicate first number

skip repeated first numbers to avoid duplicate quadruplets

if j > i + 1 and nums[j] == nums[j - 1]: continue # skip duplicate second number

skip repeated second numbers to avoid duplicate quadruplets

while left < right:

use two pointers to find pairs that complete quadruplet

total = nums[i] + nums[j] + nums[left] + nums[right]

calculate sum of current quadruplet candidates

if total == target:

found quadruplet matching target sum

left += 1; right -= 1

move pointers inward to find new pairs

while left < right and nums[left] == nums[left - 1]: left += 1

skip duplicate third numbers

while left < right and nums[right] == nums[right + 1]: right -= 1

skip duplicate fourth numbers

elif total < target: left += 1

sum too small, move left pointer right to increase sum

else: right -= 1

sum too big, move right pointer left to decrease sum

Output

[-2, -1, 1, 2]

[-2, 0, 0, 2]

[-1, 0, 0, 1]

Complexity Analysis

Time: O(n^3) because we use three 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 without sorting or skipping duplicates

Edge Cases

empty list

returns empty list, no quadruplets

DSA Python

for i in range(n - 3):

list with fewer than 4 elements

returns empty list, no quadruplets possible

DSA Python

for i in range(n - 3):

all elements are the same and sum matches target

returns one quadruplet with those elements, duplicates skipped

DSA Python

if i > 0 and nums[i] == nums[i - 1]: continue

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 first, causing difficulty skipping duplicates and using two pointers
Fix: Sort the array at the start to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for all four numbers, leading to repeated quadruplets
Fix: Add checks to skip duplicates for first, second, third, and fourth numbers

Mistake: Moving pointers incorrectly after finding a quadruplet, missing some valid sets
Fix: After finding a quadruplet, move both pointers inward and skip duplicates carefully

Summary

Find all unique sets of four numbers in a list that add up to a target sum.

Use when you need to find quadruplets summing to a target without duplicates efficiently.

Sort the list and use two nested loops plus two pointers to find quadruplets while skipping duplicates.

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 that sum to a target

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks to find all unique sets of four numbers (quadruplets) in an array that add up to a given target sum.

2. Step 2: Identify the goal

   The goal is not sorting or counting pairs but to find quadruplets with a specific sum 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 = unique quadruplets summing to target [OK]

Hint: Look for four numbers adding to target, no duplicates [OK]

Common Mistakes:

• Confusing Four Sum with Two Sum or Three Sum problems
• Thinking the problem is about sorting or counting pairs
• Ignoring the uniqueness of quadruplets

2. Which of the following Python code snippets correctly initializes an empty list to store quadruplets for the Four Sum problem?

easy

A. quadruplets = ()

B. quadruplets = []

C. quadruplets = {}

D. quadruplets = set()

Solution

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

   Quadruplets are multiple groups of four numbers, so a list is suitable to store them.

2. Step 2: Check the initialization syntax

   Using [] initializes an empty list, which is correct. Curly braces {} create a dictionary, parentheses () create a tuple, and set() creates a set which is unordered and not ideal here.

3. Final Answer:

   quadruplets = [] -> Option B

4. Quick Check:

   Empty list for quadruplets = [] [OK]

Hint: Use [] to store multiple quadruplets in a list [OK]

Common Mistakes:

• Using {} which creates a dictionary, not a list
• Using () which creates an immutable tuple
• Using set() which is unordered and may lose duplicates

3. What will be the output of the following Python code snippet for the Four Sum problem?

nums = [1, 0, -1, 0, -2, 2]
target = 0
# After sorting
nums.sort()
quadruplets = []
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:
            total = nums[i] + nums[j] + nums[left] + nums[right]
            if total == target:
                quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
print(quadruplets)

medium

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

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

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

D. []

Solution

1. Step 1: Sort the array and understand the loops

   Sorted nums = [-2, -1, 0, 0, 1, 2]. The nested loops and two-pointer approach check all quadruplets summing to target 0.

2. Step 2: Identify quadruplets that sum to zero

   Valid quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1]. These are appended to quadruplets list.

3. Final Answer:

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

4. Quick Check:

   Sum quadruplets = 0 matches output [OK]

Hint: Sort array, use two pointers inside nested loops [OK]

Common Mistakes:

• Not sorting the array before processing
• Missing some quadruplets due to pointer errors
• Appending duplicates without checks

4. Identify the bug in the following code snippet for the Four Sum problem and select the correct fix.

nums = [2, 2, 2, 2, 2]
target = 8
nums.sort()
quadruplets = []
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:
            total = nums[i] + nums[j] + nums[left] + nums[right]
            if total == target:
                quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
print(quadruplets)

medium

A. Add checks to skip duplicates for i, j, left, and right indices

B. Change quadruplets to a set to avoid duplicates

C. Remove sorting to improve performance

D. Replace while loop with a for loop

Solution

1. Step 1: Identify the problem with duplicates

   The code appends quadruplets but does not skip duplicates, so it will add the same quadruplet multiple times.

2. Step 2: Fix by skipping duplicates

   Adding checks to skip duplicate values for i, j, left, and right indices after finding a quadruplet prevents repeated quadruplets.

3. Final Answer:

   Add checks to skip duplicates for i, j, left, and right indices -> Option A

4. Quick Check:

   Skipping duplicates avoids repeated quadruplets [OK]

Hint: Skip duplicates after finding quadruplets to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates causing repeated quadruplets
• Using set without sorting can cause unordered results
• Removing sorting breaks two-pointer logic

5. Given the array nums = [1, 0, -1, 0, -2, 2, 2] and target 2, which of the following lists contains all unique quadruplets that sum to the target?

hard

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

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

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

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

Solution

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

   Sorted nums = [-2, -1, 0, 0, 1, 2, 2]. We look for quadruplets where sum equals 2.

2. Step 2: Identify valid quadruplets

   Valid quadruplets are [-2, 0, 2, 2] (sum = 2) and [-1, 0, 1, 2] (sum = 2). Other options contain invalid or impossible sums.

3. Final Answer:

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

4. Quick Check:

   Sum quadruplets = 2 matches output [OK]

Hint: Sort and check quadruplets summing exactly to target [OK]

Common Mistakes:

• Including quadruplets with wrong sums
• Ignoring duplicates or invalid numbers
• Not sorting before searching quadruplets