Arrays - 4 Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

Solution 1 - Sort input array, and generalize into a K sum problem with the intution from 2 Sum, 3 Sum problems

In this approach, we are going to sort the input array first, then generalize the solutions that we have used in TwoSum II and 3 Sum. So, we are going to reduce the k sum problem to ... 3 sum, 2 sum problems in recursive fashion.

Implementation steps:

First, we will sort the input array using an inbuilt function Arrays.sort(nums).
Then, we will create a new function kSumRecursive which takes following arguments :
- k - which tells how many numbers to be considered to get the target.
- target - the target value that we are trying to find.
- start - the starting index of nums array, where to start from.
- nums - input array.
- path - list of integers, that we are adding as we call the function recursively, which number is added out of k integers.
- result - list of quadruplets that we need to return as answer.
Next, let's write the base case for the recursive function, which is when k == 2, using a while loop and left and right bounds of array, find pairs of numbers that adds upto the target while ignoring the duplicates, and add each pair of numbers to the result.
Call the kSumRecursive function recursively, by reducing k by 1 each time, reduce the target by current number target = target - nums[i] , and increment start index by 1, to start looking next set of k-1 numbers from this index.

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class FourSum { static List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); kSumRecursive(4, target, 0, nums, new ArrayList<>(), result); return result; } static void kSumRecursive(int k, long target, int start, int[] nums, List<Integer> path, List<List<Integer>> result) { if(k == 2) { // reduced to two sum problem, this is the base case int left = start; int right = nums.length-1; while(left < right) { int currentSum = nums[left] + nums[right]; if(currentSum == target) { // Don't modify path, because we will continue checking other pairs List<Integer> temp = new ArrayList<>(path); temp.addAll(List.of(nums[left], nums[right])); result.add(temp); // for next loop, check if the next element is duplicate left++; while(left < right && nums[left] == nums[left-1]) { left++; } } else if (currentSum < target ) { left++; } else { right--; } } } else { for (int i = start; i < nums.length - k + 1; i++) { // +1 is because if there are only k elements if (i > start && nums[i] == nums[i - 1]) { continue; } List<Integer> tempPath = new ArrayList<>(path); // add current element to the ones already in path. tempPath.add(nums[i]); kSumRecursive(k - 1, target - nums[i], i + 1, nums, tempPath, result); } } } public static void main(String[] args) { System.out.println(fourSum(new int[]{1,0,-1,0,-2,2}, 0)); System.out.println(fourSum(new int[]{0, 0, 0, 0}, 0)); System.out.println(fourSum(new int[]{-3,-2,-1,0,0,1,2,3}, 0)); System.out.println(fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n ^k-1) time, in this case it is O(n³) where n is the length of input array nums. This is because two sum runs in O(n) time and there will k-2 loops above this.
Space complexity: O(k), for the temporary arrays we are using in recursion, also for the stack.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: