4 Sum - Find four elements that sum to a given target value

We are given an array A of integers and another number K. Our task is to find all the unique quadruple from the given array that sums up to K.

All the quadruples which you return should be internally sorted, ie for any quadruple [q1, q2, q3, q4], they should follow the order: q1 <= q2 <= q3 <= q4.

Example 1

Input:

N = 5, K = 3

A[] = {0,0,2,1,1}

Output: 0 0 1 2

Explanation: Sum of 0, 0, 1, 2 is equal

to K.

Example 2

Input:

N = 7, K = 23

A[] = {10,2,3,4,5,7,8}

Output:  2 3 8 10

              2 4 7 10

              3 5 7 8

Explanation: Sum of 2, 3, 8, 10 = 23,

sum of 2, 4, 7, 10 = 23 and sum of 3,

5, 7, 8 = 23.

Approach

We're using a two-pointer approach along with sorting to efficiently find all unique quadruples in the array that sum up to the given target. By sorting the array first, we ensure that duplicate elements are grouped together, making it easier to avoid redundant calculations. Then, we iterate through the array, selecting pairs of elements and using two pointers to find the remaining two elements such that their sum equals the target. This approach helps us avoid duplicates and ensures that the quadruples are internally sorted as required. Finally, we return the list of unique quadruples found.

1. Sort the input array nums.
2. Initialize an empty list result to store the quadruples.
3. Iterate over the array from index 0 to length - 4:

1. If the current element is equal to the previous element, continue to the next iteration to avoid duplicates.
2. Iterate over the array from index i + 1 to length - 3:

I. If the current element is equal to the previous element, continue to the next iteration to avoid duplicates.

II. Initialize two pointers, left and right, to track the remaining elements.

III. Calculate the target sum for the current pair of elements.

IV. Use the two-pointer approach to find pairs of elements that sum up to the target.

• If the sum is equal to the target, add the quadruple to the result list.
• Move the pointers inward and skip duplicates.

4. Return the result list containing all unique quadruples.

Complexity

• Time Complexity: O(N^3) where N is the size of the input array.
• Space Complexity: O(N^2) where N is the size of the input array.

Code

# Java Code

import java.util.*;

class FindAllFourSumNumbers {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;

                int left = j + 1, right = n - 1;
                int target2 = target - nums[i] - nums[j];

                while (left < right) {

                    int sum = nums[left] + nums[right];
                    if (sum == target2) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        while (left < right && nums[left] == nums[left + 1])
                            left++;

                        while (left < right && nums[right] == nums[right - 1])
                            right--;

                        left++;
                        right--;
                    } else if (sum < target2) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {

        FindAllFourSumNumbers solution = new FindAllFourSumNumbers();
        int[] arr1 = { 0, 0, 2, 1, 1 };
        int target1 = 3;
        List<List<Integer>> result1 = solution.fourSum(arr1, target1);

        System.out.println("Example 1:");
        for (List<Integer> quad : result1) {
            System.out.println(quad);
        }

        int[] arr2 = { 10, 2, 3, 4, 5, 7, 8 };
        int target2 = 23;
        List<List<Integer>> result2 = solution.fourSum(arr2, target2);

        System.out.println("\nExample 2:");
        for (List<Integer> quad : result2) {
            System.out.println(quad);
        }
    }
}

Output

Example 1:

[0, 0, 1, 2]


Example 2:

[2, 3, 8, 10]
[2, 4, 7, 10]
[3, 5, 7, 8]