K-Sum

Problem Statement:

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.

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]]

Example 2:

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

Constraints:

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

Solution:

// Main function to find all unique quadruplets that sum to the target
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums); // Sort the array to handle duplicates and use two-pointer technique
        return kSum(nums, 0, 4, target); // Start the k-sum process with k=4
    }
 
    // Helper function to find k numbers that sum to the target starting from index startIndex
    private List<List<Integer>> kSum(int[] nums, int startIndex, int k, long target) {
        int length = nums.length;
        List<List<Integer>> results = new ArrayList<>();
 
        // Base case: When k is 2, use two-pointer technique to find pairs
        if (k == 2) {
            int left = startIndex, right = length - 1;
            while (left < right) {
                long sum = (long) nums[left] + nums[right]; // Use long to avoid overflow
                if (sum == target) {
                    // Found a pair
                    results.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
                    // Move pointers and skip duplicates
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++; // Move left pointer to increase sum
                } else {
                    right--; // Move right pointer to decrease sum
                }
            }
        } else {
            // Recursive case: Reduce the k-sum problem to (k-1)-sum
            for (int i = startIndex; i < length - (k - 1); i++) {
                if (i > startIndex && nums[i] == nums[i - 1]) continue; // Skip duplicates
 
                // Find (k-1)-sum combinations that include nums[i]
                List<List<Integer>> subResults = kSum(nums, i + 1, k - 1, target - nums[i]);
                for (List<Integer> subResult : subResults) {
                    List<Integer> newList = new ArrayList<>(subResult);
                    newList.add(0, nums[i]); // Include nums[i] in each combination
                    results.add(newList);
                }
            }
        }
 
        return results; // Return all found combinations
    }