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.