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
- 48 lines of Java from the credited upstream file 18.java.
- The implementation visibly relies on sequence storage.
- 4 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 public List<List<Integer>> fourSum(int[] nums, int target) {3 List<List<Integer>> ans = new ArrayList<>();4 Arrays.sort(nums);5 nSum(nums, 4, target, 0, nums.length - 1, new ArrayList<>(), ans);6 return ans;7 }8 9 10 private void nSum(int[] nums, long n, long target, int l, int r, List<Integer> path,11 List<List<Integer>> ans) {12 if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n)13 return;14 if (n == 2) {15 16 while (l < r) {17 final int sum = nums[l] + nums[r];18 if (sum == target) {19 path.add(nums[l]);20 path.add(nums[r]);21 ans.add(new ArrayList<>(path));22 path.remove(path.size() - 1);23 path.remove(path.size() - 1);24 ++l;25 --r;26 while (l < r && nums[l] == nums[l - 1])27 ++l;28 while (l < r && nums[r] == nums[r + 1])29 --r;30 } else if (sum < target) {31 ++l;32 } else {33 --r;34 }35 }36 return;37 }38 39 for (int i = l; i <= r; ++i) {40 if (i > l && nums[i] == nums[i - 1])41 continue;42 path.add(nums[i]);43 nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans);44 path.remove(path.size() - 1);45 }46 }47}48