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]
]

在给定数组中找出“和为 target 的四个数”的所有解。

需要避免重复的解。

这次的答案适用N个数的和；好理解。

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:])
}

Similar Problem