Two Sum with Multiples

Problem

Given an array of integers nums and a target, return all unique pairs of values (not indices) that sum to target. Each pair should be sorted internally (smaller value first), and the list of pairs should be deduplicated.

Example

nums = [1, 5, 1, 4, 2], target = 6  ->  [[1, 5], [2, 4]]

Even though 1 appears twice, the pair [1, 5] is only reported once.

Go Solution

package main

import (
    "fmt"
    "sort"
)

func twoSumPairs(nums []int, target int) [][]int {
    seen := make(map[int]bool)
    pairs := make(map[[2]int]bool) // a sorted pair is the dedup key

    for _, v := range nums {
        comp := target - v
        if seen[comp] {
            lo, hi := comp, v
            if lo > hi {
                lo, hi = hi, lo
            }
            pairs[[2]int{lo, hi}] = true
        }
        seen[v] = true
    }

    out := make([][]int, 0, len(pairs))
    for p := range pairs {
        out = append(out, []int{p[0], p[1]})
    }
    sort.Slice(out, func(i, j int) bool { return out[i][0] < out[j][0] })
    return out
}

func main() {
    fmt.Println(twoSumPairs([]int{1, 5, 1, 4, 2}, 6)) // [[1 5] [2 4]]
}

How to Solve

1. Scan once, remembering values you have seen. For each value v, its partner is target - v. If that partner is already in the seen set, you have found a pair.
2. Normalise each pair before storing it. Sort the two values so [1,5] and [5,1] become the same key. A fixed-size array [2]int is comparable in Go, so it can be a map key directly.
3. Use a map as a set to deduplicate. Storing pairs in map[[2]int]bool means a pair that occurs many times is only kept once — that is what handles the duplicate 1.
4. Collect and sort the output. Map iteration order is random in Go, so sort the final slice (here by the first value) for a deterministic result.

Complexity

Time: O(n) to scan, plus O(p log p) to sort the p output pairs. Space: O(n) for the seen set and the pair set.