# 18. 4Sum

• Time: $O(n^3)$
• Space: $O(1)$
  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 42 43 44 45 46 47 48 49 50 class Solution { public: vector> fourSum(vector& nums, int target) { vector> ans; vector path; sort(begin(nums), end(nums)); nSum(nums, 4, target, 0, nums.size() - 1, path, ans); return ans; } private: // Finds n numbers add up to the target in [l, r]. void nSum(const vector& nums, long n, long target, int l, int r, vector& path, vector>& ans) { if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n) return; if (n == 2) { // Similar to the sub procedure in 15. 3Sum while (l < r) { const int sum = nums[l] + nums[r]; if (sum == target) { path.push_back(nums[l]); path.push_back(nums[r]); ans.push_back(path); path.pop_back(); path.pop_back(); ++l; --r; while (l < r && nums[l] == nums[l - 1]) ++l; while (l < r && nums[r] == nums[r + 1]) --r; } else if (sum < target) { ++l; } else { --r; } } return; } for (int i = l; i <= r; ++i) { if (i > l && nums[i] == nums[i - 1]) continue; path.push_back(nums[i]); nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans); path.pop_back(); } } }; 
  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 42 43 44 45 46 47 class Solution { public List> fourSum(int[] nums, int target) { List> ans = new ArrayList<>(); Arrays.sort(nums); nSum(nums, 4, target, 0, nums.length - 1, new ArrayList<>(), ans); return ans; } // Finds n numbers add up to the target in [l, r]. private void nSum(int[] nums, long n, long target, int l, int r, List path, List> ans) { if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n) return; if (n == 2) { // Similar to the sub procedure in 15. 3Sum while (l < r) { final int sum = nums[l] + nums[r]; if (sum == target) { path.add(nums[l]); path.add(nums[r]); ans.add(new ArrayList<>(path)); path.remove(path.size() - 1); path.remove(path.size() - 1); ++l; --r; while (l < r && nums[l] == nums[l - 1]) ++l; while (l < r && nums[r] == nums[r + 1]) --r; } else if (sum < target) { ++l; } else { --r; } } return; } for (int i = l; i <= r; ++i) { if (i > l && nums[i] == nums[i - 1]) continue; path.add(nums[i]); nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans); path.remove(path.size() - 1); } } } 
  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 class Solution: def fourSum(self, nums: List[int], target: int): ans = [] def nSum(l: int, r: int, target: int, n: int, path: List[int], ans: List[List[int]]) -> None: """Finds n numbers add up to the target in [l, r].""" if r - l + 1 < n or n < 2 or target < nums[l] * n or target > nums[r] * n: return if n == 2: while l < r: summ = nums[l] + nums[r] if summ == target: ans.append(path + [nums[l], nums[r]]) l += 1 while nums[l] == nums[l - 1] and l < r: l += 1 elif summ < target: l += 1 else: r -= 1 return for i in range(l, r + 1): if i > l and nums[i] == nums[i - 1]: continue nSum(i + 1, r, target - nums[i], n - 1, path + [nums[i]], ans) nums.sort() nSum(0, len(nums) - 1, target, 4, [], ans) return ans