Find four elements that sum to a given value (4-sum)
Problem
Return every unique quadruplet of values (from distinct indices) that sums to target. Do not repeat the same set of values.
Example 1
Input: nums = [1, 0, -1, 0, -2, 2], target = 0 Output: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]
Also asked as: find four elements that sum to a given value
Test cases
Case 1
Input: [1,0,-1,0,-2,2], 0 Expected (any order): [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Case 2
Input: [2,2,2,2,2], 8 Expected (any order): [[2,2,2,2]]
Case 3
Input: [0,0,0,0], 0 Expected (any order): [[0,0,0,0]]
Case 4
Input: [1,2,3], 6 Expected (any order): []
View solutionHide solution1 approach
1. Sort + fix two + two pointers
Time O(n³)Space O(1)
Two nested loops fix a and b; a two-pointer scan finds c, d for the remaining target. Skip duplicates.
function fourSum(a, target) { a.sort((x, y) => x - y); const res = []; const n = a.length; for (let i = 0; i < n - 3; i++) { if (i && a[i] === a[i - 1]) continue; for (let j = i + 1; j < n - 2; j++) { if (j > i + 1 && a[j] === a[j - 1]) continue; let l = j + 1, r = n - 1; while (l < r) { const s = a[i] + a[j] + a[l] + a[r]; if (s === target) { res.push([a[i], a[j], a[l], a[r]]); while (l < r && a[l] === a[l + 1]) l++; while (l < r && a[r] === a[r - 1]) r--; l++; r--; } else if (s < target) l++; else r--; } } } return res;}