Description
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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 nums = [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]
]

思路
3sum的延伸。
類似題: (Medium)16. 3Sum Closest
可以 把 4sum 想成 3sum + 一個數子 = 4sum
也就是說 可以換個 target , target' = target - 其中一個數字
再來求 3sum , 找到相等於 target' 則加入。
Note :

• 排除重複解
• 當找到其一相等 case 記得 還有可能有其他的: left+1 , right-1

正解

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans = []
        for i in range(len(nums)):
            
            tmptarget = target - nums[i]
            #print("tmp"+str(tmp))
            # 3 sum
            others = nums[i+1:]
            print(others)
            for j in range(len(others)):
                left = j+1
                right = len(others)-1
                while left<right:
                    if others[j]+others[left]+others[right] > tmptarget:
                        right-=1
                    elif  others[j]+others[left]+others[right] < tmptarget:
                        left+=1
                    else:
                        if [nums[i],others[j],others[left],others[right]] not in ans:
                            ans.append([nums[i],others[j],others[left],others[right]])
                        left+=1
                        right-=1
                        #break
        return ans                 

Result