4Sum
Medium · Two Pointers · Explanation and code example
K-Sum + Two Pointers
How it works
We can generalize the approach to solve K-Sum for any K using recursion. The idea is to reduce the problem: for K > 2, we fix one element and recursively solve (K-1)-Sum. When K reaches 2, we use the two-pointer technique as the base case. This approach is flexible and can handle any value of K without changing the core logic.
Steps
- Sort the array.
- Define a recursive function
kSum(k, start, target):- Base case (
k == 2): Use two pointers fromstartto find pairs summing to target. - Recursive case: For each element at index
ifromstart, recursively callkSum(k - 1, i + 1, target - nums[i]). - Skip duplicates at each recursion level.
- Track the current partial solution in a list, adding/removing elements as we recurse.
- Base case (
- Call
kSum(4, 0, target)and return the collected results.
Complexity
- Time complexity:
O(n ^ 3) - Space complexity:
O(1)orO(n)space depending on the sorting algorithm.O(m)space for the output array.
Things to watch for
Integer Overflow
When summing four integers, the result can exceed the 32-bit integer range. Always use a 64-bit type (like long in Java/C++) for the sum calculation to avoid overflow.
Incorrect Duplicate Skipping
When skipping duplicates, you must check against the previous element, not the next one. Also, the skip should only happen after processing the first occurrence, not before.
Forgetting to Sort the Array
The two-pointer technique only works on a sorted array. Forgetting to sort first will cause the algorithm to miss valid quadruplets or produce incorrect results.
Python code example
from typing import List
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res, quad = [], []
def kSum(k, start, target):
if k == 2:
l, r = start, len(nums) - 1
while l < r:
if nums[l] + nums[r] < target:
l += 1
elif nums[l] + nums[r] > target:
r -= 1
else:
res.append(quad + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
return
for i in range(start, len(nums) - k + 1):
if i > start and nums[i] == nums[i - 1]:
continue
quad.append(nums[i])
kSum(k - 1, i + 1, target - nums[i])
quad.pop()
kSum(4, 0, target)
return res
C++ code example
class Solution {
vector<vector<int>> res;
vector<int> quad;
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if (nums.size() < 4) return {};
sort(nums.begin(), nums.end());
kSum(nums, 4, 0, (long long) target);
return res;
}
private:
void kSum(vector<int>& nums, int k, int start, long long target) {
if (k == 2) {
int l = start, r = nums.size() - 1;
while (l < r) {
long long sum = (long long) nums[l] + nums[r];
if (sum < target) {
l++;
} else if (sum > target) {
r--;
} else {
quad.push_back(nums[l]);
quad.push_back(nums[r]);
res.push_back(quad);
quad.pop_back();
quad.pop_back();
l++;
r--;
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;
}
}
return;
}
for (int i = start; i < nums.size() - k + 1; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
quad.push_back(nums[i]);
kSum(nums, k - 1, i + 1, target - nums[i]);
quad.pop_back();
}
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.