Four Sum Problem All Unique Quadruplets in DSA Rust

Mental Model

Find four numbers in a list that add up to a target without repeating quadruplets.

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

nums: [1, 0, -1, 0, -2, 2]
indexes:  0  1   2  3   4  5
quadruplet: [a, b, c, d]
          ↑  ↑  ↑  ↑
          |  |  |  |-- last pointer moving to find sum
          |  |  |----- third pointer
          |  |-------- second pointer
          |----------- first pointer

Dry Run Walkthrough

Input: nums: [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 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 pointer at index 0 (-2), second pointer at index 1 (-1)

[-2, -1, 0, 0, 1, 2]
first=0(-2), second=1(-1)

Why: Start searching pairs for the remaining two numbers

Step 3: Use two pointers: left=2(0), right=5(2), sum = -2 + -1 + 0 + 2 = -1 < 0, move left forward

[-2, -1, 0, 0, 1, 2]
first=0(-2), second=1(-1), left=3(0), right=5(2)

Why: Sum less than target, move left pointer to increase sum

Step 4: Sum = -2 + -1 + 0 + 2 = -1 < 0, move left forward to 4(1)

[-2, -1, 0, 0, 1, 2]
first=0(-2), second=1(-1), left=4(1), right=5(2)

Why: Still less than target, move left pointer

Step 5: Sum = -2 + -1 + 1 + 2 = 0, quadruplet found [-2, -1, 1, 2], move left and right to avoid duplicates

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

Why: Found a valid quadruplet, now skip duplicates

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

[-2, -1, 0, 0, 1, 2]
first=0(-2), second=2(0), left=3(0), right=5(2)

Why: Try new second pointer to find other quadruplets

Step 7: Sum = -2 + 0 + 0 + 2 = 0, quadruplet found [-2, 0, 0, 2], move left and right to avoid duplicates

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

Why: Found another valid quadruplet

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

first=1(-1), second=2(0), left=3(0), right=5(2)

Why: Try new first pointer to find more quadruplets

Step 9: Sum = -1 + 0 + 0 + 2 = 1 > 0, move right pointer left to 4(1)

first=1(-1), second=2(0), left=3(0), right=4(1)

Why: Sum too big, decrease by moving right pointer

Step 10: 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: Found last valid quadruplet

Result:

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

Annotated Code

DSA Rust

fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let mut nums = nums;
    nums.sort();
    let mut quadruplets = Vec::new();
    let n = nums.len();
    for i in 0..n {
        if i > 0 && nums[i] == nums[i - 1] { continue; }
        for j in i + 1..n {
            if j > i + 1 && nums[j] == nums[j - 1] { continue; }
            let mut left = j + 1;
            let mut right = n - 1;
            while left < right {
                let sum = nums[i] + nums[j] + nums[left] + nums[right];
                if sum == target {
                    quadruplets.push(vec![nums[i], nums[j], nums[left], nums[right]]);
                    left += 1;
                    right -= 1;
                    while left < right && nums[left] == nums[left - 1] { left += 1; }
                    while left < right && nums[right] == nums[right + 1] { right -= 1; }
                } else if sum < target {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
    }
    quadruplets
}

fn main() {
    let nums = vec![1, 0, -1, 0, -2, 2];
    let target = 0;
    let result = four_sum(nums, target);
    for quad in result {
        println!("{}", quad.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(", "));
    }
}

nums.sort();

sort array to enable two-pointer technique and skip duplicates

if i > 0 && nums[i] == nums[i - 1] { continue; }

skip duplicate first elements to avoid repeated quadruplets

if j > i + 1 && nums[j] == nums[j - 1] { continue; }

skip duplicate second elements

while left < right {

two-pointer loop to find pairs that complete quadruplet

let sum = nums[i] + nums[j] + nums[left] + nums[right];

calculate current sum of four elements

if sum == target { quadruplets.push(...); left += 1; right -= 1; ... }

found quadruplet, add to result and move pointers skipping duplicates

else if sum < target { left += 1; } else { right -= 1; }

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 without sorting or skipping duplicates

Edge Cases

empty array

returns empty list, no quadruplets

DSA Rust

let n = nums.len(); for i in 0..n { ... }

array with less than 4 elements

returns empty list, no quadruplets possible

DSA Rust

let n = nums.len(); for i in 0..n { ... }

all elements same and sum matches target

returns one quadruplet with those elements, no duplicates

DSA Rust

if i > 0 && 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 before processing, causing duplicate quadruplets and inefficient search.
Fix: Sort the array first to enable skipping duplicates and two-pointer technique.

Mistake: Not skipping duplicates for first and second pointers, leading to repeated quadruplets.
Fix: Add checks to continue loop if current element equals previous for i and j.

Mistake: Incorrectly moving pointers after finding a quadruplet, missing some valid sets or duplicates.
Fix: After finding quadruplet, move both pointers and skip duplicates carefully.

Summary

Finds all unique sets of four numbers that add up to a target value.

Use when you need to find quadruplets summing to a target 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. Count the number of pairs with a given sum

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

C. Find the maximum element in the array

D. Sort the array in ascending order

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the goal

   The goal is not sorting or counting pairs, but specifically finding quadruplets whose sum equals the target.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing Four Sum with sorting problems
• Looking for pairs instead of quadruplets
• Ignoring uniqueness of quadruplets

2. Which Rust syntax correctly declares a vector of integers named nums?

easy

A. let nums = {1, 2, 3, 4};

B. let nums = [1, 2, 3, 4];

C. let nums = (1, 2, 3, 4);

D. let nums = vec![1, 2, 3, 4];

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, vectors are created using vec![elements] macro, which creates a growable array.

2. Step 2: Check each option

   let nums = vec![1, 2, 3, 4]; uses vec![1, 2, 3, 4] which is correct. let nums = [1, 2, 3, 4]; is an array, not a vector. let nums = (1, 2, 3, 4); is a tuple. let nums = {1, 2, 3, 4}; is invalid syntax.

3. Final Answer:

   let nums = vec![1, 2, 3, 4]; -> Option D

4. Quick Check:

   Vector syntax = vec![...] [OK]

Hint: Use vec! macro for vectors, arrays use brackets only [OK]

Common Mistakes:

• Using array syntax when vector is needed
• Confusing tuples with vectors
• Using curly braces which are invalid here

3. What is the output of the following Rust code snippet that finds quadruplets summing to 0?

let nums = vec![1, 0, -1, 0, -2, 2];
let target = 0;
// Assume function four_sum returns Vec of quadruplets
let result = four_sum(nums, target);
println!("{:?}", result);

Assuming four_sum is correctly implemented, what is the printed output?

medium

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

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

C. [[0, 0, 0, 0]]

D. []

Solution

1. Step 1: Understand the input and target

   The input array is [1, 0, -1, 0, -2, 2] and target sum is 0. We want all unique quadruplets that sum to 0.

2. Step 2: Identify all quadruplets summing to 0

   Possible quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1]. These are unique and sum to 0.

3. Final Answer:

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

4. Quick Check:

   Quadruplets sum to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array and find quadruplets summing to target [OK]

Common Mistakes:

• Returning incomplete quadruplets
• Ignoring duplicates
• Returning empty list incorrectly

4. Identify the bug in this Rust code snippet for the Four Sum problem:

fn four_sum(nums: Vec<i32>, target: i32) -> Vec {
    let mut nums = nums;
    nums.sort();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        for j in i+1..nums.len() {
            let mut left = j + 1;
            let mut right = nums.len() - 1;
            while left < right {
                let sum = nums[i] + nums[j] + nums[left] + nums[right];
                if sum == target {
                    result.push(vec![nums[i], nums[j], nums[left], nums[right]]);
                    left += 1;
                    right -= 1;
                } else if sum < target {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
    }
    result
}

What is the main issue causing duplicate quadruplets in the result?

medium

A. The vector nums is not sorted before processing

B. The while loop condition left < right is incorrect and should be left <= right

C. The code does not skip duplicate values for i, j, left, and right indices after finding a quadruplet

D. The function does not return the result vector

Solution

1. Step 1: Analyze duplicate handling in loops

   The code finds quadruplets but does not skip over duplicate values for indices i, j, left, and right after adding a quadruplet, causing duplicates in the result.

2. Step 2: Check other options

   The vector is sorted correctly, the while loop condition is correct, and the function returns the result vector properly.

3. Final Answer:

   The code does not skip duplicate values for i, j, left, and right indices after finding a quadruplet -> Option C

4. Quick Check:

   Skipping duplicates needed to avoid repeated quadruplets [OK]

Hint: Skip duplicates after adding quadruplet to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates for all pointers
• Changing loop conditions incorrectly
• Forgetting to sort the array

5. Given the array nums = [2, 2, 2, 2, 2] and target 8, what is the correct output of a Four Sum function that returns all unique quadruplets summing to the target?

hard

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

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

C. []

D. [[2, 2, 2]]

Solution

1. Step 1: Understand the input and target

   The array contains five 2's and the target sum is 8. We need quadruplets of four numbers summing to 8.

2. Step 2: Identify unique quadruplets

   Only one unique quadruplet exists: [2, 2, 2, 2]. Although multiple combinations exist, duplicates must be avoided.

3. Final Answer:

   [[2, 2, 2, 2]] -> Option A

4. Quick Check:

   Unique quadruplet summing to 8 = [[2, 2, 2, 2]] [OK]

Hint: Avoid duplicates; only one quadruplet of identical numbers [OK]

Common Mistakes:

• Returning duplicate quadruplets multiple times
• Returning empty list incorrectly
• Returning triples instead of quadruplets