Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
def kSum(nums, start, target, k):
if nums[0] * k > target or nums[-1] * k < target:
return []
res = []
if k == 2:
return twoSum(nums, start, target)
for i in range(start, len(nums) - k + 1):
if i > start and nums[i] == nums[i - 1]:
continue
for x in kSum(nums, i + 1, target - nums[i], k - 1):
res.append([nums[i]] + x)
return res
def twoSum(nums, start, target):
low = start
high = len(nums) - 1
res = []
while low < high:
s = nums[low] + nums[high]
if s < target or (low != start and nums[low] == nums[low - 1]):
low += 1
elif s > target or (high != len(nums) - 1 and nums[high] == nums[high + 1]):
high -= 1
else:
res.append(([nums[low], nums[high]]))
low += 1
high -= 1
return res
return kSum(nums, 0, target, 4)