ソートとツーポインタで和が目標になる 4 つの組を全部集める

def four_sum(nums, target):
    a = sorted(nums)
    return k_sum(
        a, 0, 4, target
    )


def k_sum(a, lo, k, goal):
    if k == 2:
        return two_sum(
            a, lo, goal
        )
    out = []
    for i in range(lo, len(a)):
        if dup(a, i, lo):
            continue
        x = a[i]
        subs = k_sum(
            a, i + 1, k - 1,
            goal - x,
        )
        for t in subs:
            out.append([x] + t)
    return out


def two_sum(a, lo, goal):
    start = lo
    hi = len(a) - 1
    out = []
    while lo < hi:
        if dup(a, lo, start):
            lo += 1
            continue
        x = a[lo]
        y = a[hi]
        if x + y < goal:
            lo += 1
        elif x + y > goal:
            hi -= 1
        else:
            out.append([x, y])
            lo += 1
            hi -= 1
    return out


def dup(a, i, first):
    if i == first:
        return False
    return a[i] == a[i - 1]

function fourSum(nums, target) {
  const a = [...nums].sort(
    (p, q) => p - q
  );
  return kSum(a, 0, 4, target);
}

function kSum(
  a, lo, k, goal
) {
  if (k === 2) {
    return twoSum(a, lo, goal);
  }
  const out = [];
  const n = a.length;
  for (let i = lo; i < n; i++) {
    if (dup(a, i, lo)) {
      continue;
    }
    const x = a[i];
    const rest = goal - x;
    const subs = kSum(
      a, i + 1, k - 1, rest
    );
    for (const t of subs) {
      out.push([x, ...t]);
    }
  }
  return out;
}

function twoSum(a, lo, goal) {
  const start = lo;
  let hi = a.length - 1;
  const out = [];
  while (lo < hi) {
    if (dup(a, lo, start)) {
      lo++;
      continue;
    }
    const x = a[lo];
    const y = a[hi];
    if (x + y < goal) {
      lo++;
    } else if (x + y > goal) {
      hi--;
    } else {
      out.push([x, y]);
      lo++;
      hi--;
    }
  }
  return out;
}

function dup(a, i, first) {
  if (i === first) {
    return false;
  }
  return a[i] === a[i - 1];
}

import "sort"

func fourSum(
	nums []int, target int,
) [][]int {
	a := append([]int{}, nums...)
	sort.Ints(a)
	return kSum(a, 0, 4, target)
}

func kSum(
	a []int, lo, k, goal int,
) [][]int {
	if k == 2 {
		return twoSum(a, lo, goal)
	}
	out := [][]int{}
	for i := lo; i < len(a); i++ {
		if dup(a, i, lo) {
			continue
		}
		x := a[i]
		subs := kSum(
			a, i+1, k-1, goal-x,
		)
		for _, t := range subs {
			q := []int{x}
			q = append(q, t...)
			out = append(out, q)
		}
	}
	return out
}

func twoSum(
	a []int, lo, goal int,
) [][]int {
	start := lo
	hi := len(a) - 1
	out := [][]int{}
	for lo < hi {
		if dup(a, lo, start) {
			lo++
			continue
		}
		x, y := a[lo], a[hi]
		if x+y < goal {
			lo++
		} else if x+y > goal {
			hi--
		} else {
			p := []int{x, y}
			out = append(out, p)
			lo++
			hi--
		}
	}
	return out
}

func dup(
	a []int, i, first int,
) bool {
	if i == first {
		return false
	}
	return a[i] == a[i-1]
}