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.
Example
Given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
1
2
3
4
5
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
Solution
Be careful to skip all repeated elements
(4Sum.py) download 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
class Solution ( object ):
def fourSum ( self , nums , target ):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not nums :
return nums
nums = sorted ( nums )
ret = []
n = len ( nums )
for i in range ( 0 , n - 3 ):
# skip all redundant element
if i != 0 and nums [ i ] == nums [ i - 1 ]:
continue
for j in range ( n - 1 , i + 2 , - 1 ):
# skipp repeated elements
if j != n - 1 and nums [ j ] == nums [ j + 1 ]:
continue
l = i + 1
r = j - 1
while l < r :
val = nums [ i ] + nums [ j ] + nums [ l ] + nums [ r ]
if val == target :
ret . append ([ nums [ i ], nums [ l ], nums [ r ], nums [ j ]])
l += 1
r -= 1
# skip repeated element
while l < r and nums [ l ] == nums [ l - 1 ]:
l += 1
while l < r and nums [ r ] == nums [ r + 1 ]:
r = r - 1
elif val < target :
l = l + 1
else :
r = r - 1
return ret