4Sum

                                            
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        
        def findNsum(nums, target, N, result, results):
            if len(nums) < N or N < 2 or target < nums[0] * N or target > nums[-1] * N:
                return
            if N == 2:
                l, r = 0, len(nums) - 1
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else:
                for i in range(len(nums) - N + 1):
                    if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
                        findNsum(nums[i + 1:], target - nums[i], N - 1, result + [nums[i]], results)
        
        findNsum(nums, target, 4, [], res)
        return res

                                            
function fourSum(nums: number[], target: number): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    
    if (n < 4) {
        return result;
    }
    
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            
            let left = j + 1;
            let right = n - 1;
            
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                
                if (sum === target) {
                    result.push([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 < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    function fourSum($nums, $target) {
        $result = [];
        sort($nums);
        $n = count($nums);
        
        for ($i = 0; $i < $n - 3; $i++) {
            if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
                continue;
            }
            
            for ($j = $i + 1; $j < $n - 2; $j++) {
                if ($j > $i + 1 && $nums[$j] == $nums[$j - 1]) {
                    continue;
                }
                
                $left = $j + 1;
                $right = $n - 1;
                
                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    
                    if ($sum == $target) {
                        $result[] = [$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--;
                    } elseif ($sum < $target) {
                        $left++;
                    } else {
                        $right--;
                    }
                }
            }
        }
        
        return $result;
    }
}

                                            
class Solution {
  List<List<int>> fourSum(List<int> nums, int target) {
      List<List<int>> result = [];
      if (nums == null || nums.length < 4) {
          return result;
      }
      nums.sort();
      for (int i = 0; i < nums.length - 3; i++) {
          if (i > 0 && nums[i] == nums[i - 1]) {
              continue;
          }
          for (int j = i + 1; j < nums.length - 2; j++) {
              if (j > i + 1 && nums[j] == nums[j - 1]) {
                  continue;
              }
              int left = j + 1;
              int right = nums.length - 1;
              while (left < right) {
                  int sum = nums[i] + nums[j] + nums[left] + nums[right];
                  if (sum == target) {
                      result.add([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 < target) {
                      left++;
                  } else {
                      right--;
                  }
              }
          }
      }
      return result;
  }
}

                                            
func fourSum(nums []int, target int) [][]int {
    var res [][]int
    if len(nums) < 4 {
        return res
    }
    
    sort.Ints(nums)
    
    for i := 0; i < len(nums)-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i+1; j < len(nums)-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            left := j + 1
            right := len(nums) - 1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                if sum == target {
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
                    for left < right && nums[left] == nums[left+1] {
                        left++
                    }
                    for left < right && nums[right] == nums[right-1] {
                        right--
                    }
                    left++
                    right--
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    
    return res
}

                                            
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[][]}
def four_sum(nums, target)
    nums.sort!
    results = []
    find_n_sum(nums, target, 4, [], results)
    results
end

def find_n_sum(nums, target, n, temp, results)
    return if nums.length < n || n < 2 || target < nums.first * n || target > nums.last * n
    
    if n == 2
        left, right = 0, nums.length - 1
        while left < right
            sum = nums[left] + nums[right]
            if sum == target
                results.push(temp + [nums[left], nums[right]])
                left += 1
                right -= 1
                left += 1 while left < right && nums[left] == nums[left - 1]
                right -= 1 while left < right && nums[right] == nums[right + 1]
            elsif sum < target
                left += 1
            else
                right -= 1
            end
        end
    else
        (0..nums.length - n).each do |i|
            next if i > 0 && nums[i] == nums[i - 1]
            find_n_sum(nums[i + 1..-1], target - nums[i], n - 1, temp + [nums[i]], results)
        end
    end
end

To solve this coding challenge, we need to find all unique quadruplets in a given array that sum up to a specific target. The quadruplets must be distinct, meaning none of the indices in any of the quadruplets should be the same. We'll leverage a recursive approach to break down the problem into more manageable sub-problems, eventually utilizing a two-pointer technique for the base case.

# Explanation:

We utilize a recursive function
findNsum

to reduce the N-sum problem into smaller problems until we reach the 2-sum problem.
First, we sort the array
nums

to facilitate the two-pointer technique for the 2-sum problem.
The
findNsum

function works as follows:

Base case: If
N

equals 2 (i.e., looking for pairs), use a two-pointer technique to find pairs that sum up to the reduced target.
Recursive case: For
N > 2

, loop through the array, and recursively reduce the problem to an (N-1)-sum problem while adjusting the target accordingly.

To ensure uniqueness, skip the elements that are the same as the previous one during iteration.
The main function initializes the recursion and sorts the result before returning it.

# Detailed Steps in Pseudocode:

Sort the array : Sorting helps to use the two-pointer technique effectively.
Recursive function : Define a recursive function
findNsum

.

Parameters : Input array
nums

, current target
current_target

, integer
N

(indicating the N-sum problem),
current_result

(stores the current quadruplet being constructed), and
all_results

(stores all valid quadruplets).

Base case for recursion :

If
N

is 2, use two pointers (
left

and
right

) to find pairs that sum up to
current_target

.
Adjust pointers and skip duplicates.

Recursive case :

Iterate through the array, recursively call
findNsum

to reduce the problem to (N-1)-sum, and adjust the target by subtracting the current element.

Initialize and call the recursion : Call
findNsum

from the main function with initial parameters.
Return results : Return the list of unique quadruplets.

# Pseudocode:

                                            
# Function to find N unique numbers summing to target

def findNsum(nums, current_target, N, current_result, all_results):
    # if the length of nums is less than N or impossible to find a sum based on boundary conditions, return
    if len(nums) < N or N < 2 or current_target < nums[0] * N or current_target > nums[-1] * N:
        return
    
    # Base case: If looking for pairs (N == 2)
    if N == 2:
        left, right = 0, len(nums) - 1
        
        # Two-pointer technique to find pairs 
        while left < right:
            current_sum = nums[left] + nums[right]
            
            # Check if current pair sums to the target
            if current_sum == current_target:
                # Add found pair to results
                all_results.append(current_result + [nums[left], nums[right]])
                left += 1
                # Skip duplicates
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
            elif current_sum < current_target:
                left += 1
            else:
                right -= 1
                
    else:
        # Recursive reduction for N-sum problem
        for i in range(len(nums) - N + 1):
            # Avoid duplicate results by skipping duplicates
            if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
                # Recursively reduce the problem to an (N-1)-sum problem
                findNsum(nums[i + 1:], current_target - nums[i], N - 1, current_result + [nums[i]], all_results)


# Main function to find all unique quadruplets
def fourSum(nums, target):
    all_results = []  # List to store all unique quadruplets
    nums.sort()       # Sort the array to facilitate the two-pointer approach for the 2-sum problem
    findNsum(nums, target, 4, [], all_results)  # Start the recursion for 4-sum
    return all_results

# Example usage:
# print(fourSum([1, 0, -1, 0, -2, 2], 0))  # Expected output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

This detailed methodology leverages sorting, recursion, and the two-pointer technique in pseudocode to precisely find all unique quadruplets summing up to a target value.