Solution in Python 3 (beats 100.00%) (48 ms) ( O(n³) ) (Asymptotic Analysis)
Asymptotic Worst Case Analysis:\nFor ease of analysis, we will assume that the input list is sorted since sorting only takes O(n log n) time. The worst case occ
_Asymptotic Worst Case Analysis:_\nFor ease of analysis, we will assume that the input list is sorted since sorting only takes O(n log n) time. The worst case occurs if the target is equal to the sum of the four greatest elements in the list. This is because the search would have to continue until the very end to find the desired quadruplet _(a,b,c,d)_. For example, a list of the form _N_ = [1,2,3,4,5,6,7,8,9,10] with _target_ = 34 would require a complete run through all iterations of the three nested for loops. Note that the reason that there are only three nested for loops even though we are looking for a quadruplet is because finding the triplet _(a,b,c)_ determines a unique value of _d_ which will lead to a sum of _target_. Thus, we only need to search for triplets _(a,b,c)_ such that _target - (a+b+c)_ is in the original list.\n\nObserve that in the worst case, there is only one valid solution and that is found by adding the last four (i.e. the largest four) elements of the input list. Specifically, the desired quadruplet will be _( N[n-4], N[n-3], N[n-2], N[n-1] )_, where _N_ is the sorted input list and _n_ is its length. The outer for loop will have to iterate from _i_ = 1 to _i_ = _n-5_ with a guarantee of failure in finding the desired quadruplet since the lowest element in the desired quadrauplet occurs at index _n-4_. For each iteration of the outer for loop, the remaining two nested inner for loops iterate through the remaining elements to the right of index _i_, looking at all possible ordered pairs _(b,c)_ such that _target - (a+b+c)_ is in the original list. This is an O(n\xB2) search that occurs _within_ each iteration of the outer for loop. It is guaranteed to fail in the worst case for outer loop indices from _i_ = 1 to _i_ = _n-5_. Thus in the worst case this algorithm is O(n\xB3).\n```\nclass Solution:\n    def fourSum(self, n: List[int], t: int) -> List[List[int]]:\n    \tif not n: return []\n    \tn.sort()\n    \tL, N, S, M = len(n), {j:i for i,j in enumerate(n)}, set(), n[-1]\n    \tfor i in range(L-3):\n    \t\ta = n[i]\n    \t\tif a + 3*M < t: continue\n    \t\tif 4*a > t: break\n    \t\tfor j in range(i+1,L-2):\n    \t\t\tb = n[j]\n    \t\t\tif a + b + 2*M < t: continue\n    \t\t\tif a + 3*b > t: break\n    \t\t\tfor k in range(j+1,L-1):\n    \t\t\t\tc = n[k]\n    \t\t\t\td = t-(a+b+c)\n    \t\t\t\tif d > M: continue\n    \t\t\t\tif d < c: break\n    \t\t\t\tif d in N and N[d] > k: S.add((a,b,c,d))\n    \treturn S\n\t\t\n\t\t\n- Junaid Mansuri\n(LeetCode ID)@hotmail.com
['Python', 'Python3']