4Sum

func fourSum(nums []int, target int) [][]int {

}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
    }
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
    }
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
        }
    }
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            // Converging scan for the last two numbers.
        }
    }
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            // Converging scan for the last two numbers.
            left, right := j+1, n-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
            }
        }
    }
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            // Converging scan for the last two numbers.
            left, right := j+1, n-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                // Too small: grow the sum.

                // Too big: shrink the sum.
            }
        }
    }
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            // Converging scan for the last two numbers.
            left, right := j+1, n-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                switch {
                // Too small: grow the sum.
                case sum < target:
                    left++

                // Too big: shrink the sum.
                case sum > target:
                    right--
                }
            }
        }
    }
}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            // Converging scan for the last two numbers.
            left, right := j+1, n-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                switch {
                // Too small: grow the sum.
                case sum < target:
                    left++

                // Too big: shrink the sum.
                case sum > target:
                    right--

                // Match: record it, step both pointers in, then skip duplicate
                // values on each side so quadruplets stay unique.
                }
            }
        }
    }

}

func fourSum(nums []int, target int) [][]int {
    // 4Sum is 3Sum with one more fixed number: two nested anchors (i, j), then
    // the converging scan on what's left.
    sort.Ints(nums)
    n := len(nums)
    res := [][]int{}

    // First anchor. Skip a repeated value so we don't emit duplicate quadruplets.
    for i := 0; i < n-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Second anchor. Skip repeats among j's — but not i+1 itself, which is
        // the first legal j for this i.
        for j := i + 1; j < n-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            // Converging scan for the last two numbers.
            left, right := j+1, n-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                switch {
                // Too small: grow the sum.
                case sum < target:
                    left++

                // Too big: shrink the sum.
                case sum > target:
                    right--

                // Match: record it, step both pointers in, then skip duplicate
                // values on each side so quadruplets stay unique.
                default:
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
                    left++
                    right--
                    for left < right && nums[left] == nums[left-1] {
                        left++
                    }
                    for left < right && nums[right] == nums[right+1] {
                        right--
                    }
                }
            }
        }
    }

    return res // O(n^3)
}