NUHMAN.com

Introduction

LeetCode 18: 4Sum is an extension of the 2Sum and 3Sum problems. The challenge is to find all unique quadruplets in the array which sum up to a given target value.

In this article, we’ll solve 4Sum using sorting + two pointers + pruning for an efficient and readable solution in Go (Golang).

Problem Statement

Given an array nums of n integers, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

r

0 <= a, b, c, d < n
a, b, c, and d are distinct
nums[a] + nums[b] + nums[c] + nums[d] == target

Return the result list without duplicate quadruplets.

Examples

go

Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
go

Input: nums = [2, 2, 2, 2, 2], target = 8
Output: [[2, 2, 2, 2]]

Approach: Sort + Two Pointers + Pruning

1. Sort the array to make it easier to skip duplicates and apply two pointers.
2. Fix two indices (i, j) in nested loops.
3. Use two pointers (left, right) to find the remaining two values.
4. Skip duplicates for all four elements.
5. Prune early if the smallest or largest sums can’t hit the target.

Go Implementation

go

package main

import (
    "fmt"
    "sort"
)

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    var result [][]int
    n := len(nums)

    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            left, right := j + 1, n - 1

            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]

                if sum == target {
                    result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})

                    // Skip duplicates for left and right
                    for left < right && nums[left] == nums[left+1] {
                        left++
                    }
                    for left < right && nums[right] == nums[right-1] {
                        right--
                    }

                    left++
                    right--
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }

    return result
}

func main() {
    testCases := []struct {
        nums   []int
        target int
    }{
        {[]int{1, 0, -1, 0, -2, 2}, 0},
        {[]int{2, 2, 2, 2, 2}, 8},
        {[]int{-3, -1, 0, 2, 4, 5}, 2},
    }

    for _, tc := range testCases {
        fmt.Printf("Input: %v, Target: %d -> Quadruplets: %v\n", tc.nums, tc.target, fourSum(tc.nums, tc.target))
    }
}

Step-by-Step Example: [1, 0, -1, 0, -2, 2], Target = 0

Sorted array: [-2, -1, 0, 0, 1, 2]

• i = 0 (-2), j = 1 (-1)
• left = 2 (0), right = 5 (2)
• sum = -2 + -1 + 0 + 2 = -1 → left++
• sum = -2 + -1 + 0 + 2 = -1 → left++
• sum = -2 + -1 + 1 + 2 = 0 → ✅ append
• skip duplicates and continue

Continue checking other combinations...

Final result: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Time and Space Complexity

• Time Complexity: O(n³)
• Two outer loops + inner two-pointer loop
• Space Complexity: O(1) (excluding output)

Key Takeaways

• Sorting helps detect and skip duplicates.
• Two-pointer strategy makes it faster than brute force.
• Prune unnecessary paths to reduce computation.
• This approach can be extended to k-Sum problems.