4Sum

## Description

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

``````For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
``````

## Solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 `````` ``````func fourSum(nums []int, target int) [][]int { sort.Ints(nums) return sum(nums, target, 4) } func sum(nums []int, target int, n int) [][]int { if len(nums) < n || // not enough numbers sumOfSlice(nums[len(nums)-n:]) < target || // max-sum still smaller than target sumOfSlice(nums[:n]) > target { // min-sum still bigger than target // no answer return [][]int{} } res := make([][]int, 0) for i := 0; i < len(nums); i++{ num := nums[i] if n == 1 && num == target { return [][]int{ []int{num}, } } else if n > 1 { // let's suppose num is one of the n numbers // so the other n-1 numbers' sum is target-num // then search the rest numbers for _, r := range sum(nums[i+1:], target-num, n-1) { res = append(res, append(r, num)) } // skip the same numbers for j := i + 1; j < len(nums) && nums[j] == num; j++ { i++ } } } return res } // get sum of slice func sumOfSlice(nums []int) int { if len(nums) == 1 { return nums[0] } return nums[0] + sumOfSlice(nums[1:]) }``````