Four Sum Problem All Unique Quadruplets in DSA Python - Build from Scratch

Four Sum Problem All Unique Quadruplets

📖 Scenario: You are working on a shopping app that suggests combinations of four products whose prices add up to a customer's gift card value. To help the app, you need to find all unique sets of four product prices that sum to the gift card amount.

🎯 Goal: Build a Python program that finds all unique quadruplets in a list of integers that sum up to a given target value.

📋 What You'll Learn

Create a list called nums with the exact values: [1, 0, -1, 0, -2, 2]

Create an integer variable called target and set it to 0

Write a function called four_sum that takes nums and target as parameters and returns a list of unique quadruplets that sum to target

Print the result of calling four_sum(nums, target)

💡 Why This Matters

🌍 Real World

Finding combinations of products or items that meet a specific budget or target sum is common in shopping apps, budgeting tools, and financial planning software.

💼 Career

Understanding how to find unique combinations in data sets is useful for software engineers working on recommendation systems, data analysis, and algorithm optimization.

1

Create the list of numbers

Create a list called nums with these exact values: [1, 0, -1, 0, -2, 2]

DSA Python

# Create the list nums with the given values
# Your code here

Hint

Use square brackets to create the list and separate numbers with commas.

2

Set the target sum

Create an integer variable called target and set it to 0

DSA Python

nums = [1, 0, -1, 0, -2, 2]
# Create the integer variable target and set it to 0
# Your code here

Hint

Use a simple assignment to create the variable.

3

Write the function to find unique quadruplets

Write a function called four_sum that takes nums and target as parameters and returns a list of unique quadruplets that sum to target. Use sorting and two pointers inside nested loops to find quadruplets without duplicates.

DSA Python

nums = [1, 0, -1, 0, -2, 2]
target = 0
# Define the function four_sum(nums, target) below
# Your code here

Hint

Sort the list first. Use two nested loops for the first two numbers, then use two pointers to find the other two numbers. Skip duplicates to avoid repeated quadruplets.

4

Print the result of the function

Print the result of calling four_sum(nums, target)

DSA Python

nums = [1, 0, -1, 0, -2, 2]
target = 0

def four_sum(nums, target):
    nums.sort()
    quadruplets = []
    n = len(nums)
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left = j + 1
            right = 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
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return quadruplets

# Print the result of four_sum(nums, target)
# Your code here

Hint

Use print(four_sum(nums, target)) to show the result.