Approach
Sorting and greedy selection
For 4Sum, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 34 lines of Python from the credited upstream file 18.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def fourSum(self, nums: list[int], target: int):3 ans = []4 5 def nSum(6 l: int, r: int, target: int, n: int, path: list[int],7 ans: list[list[int]]) -> None:8 """Finds n numbers that add up to the target in [l, r]."""9 if r - l + 1 < n or n < 2 or target < nums[l] * n or target > nums[r] * n:10 return11 if n == 2:12 while l < r:13 summ = nums[l] + nums[r]14 if summ == target:15 ans.append(path + [nums[l], nums[r]])16 l += 117 while nums[l] == nums[l - 1] and l < r:18 l += 119 elif summ < target:20 l += 121 else:22 r -= 123 return24 25 for i in range(l, r + 1):26 if i > l and nums[i] == nums[i - 1]:27 continue28 29 nSum(i + 1, r, target - nums[i], n - 1, path + [nums[i]], ans)30 31 nums.sort()32 nSum(0, len(nums) - 1, target, 4, [], ans)33 return ans34