16. 4 Sum

Topic :

arrays

Difficulty :

medium

Problem Link :

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
-109 <= nums[i] <= 109
-109 <= target <= 109

solution

import java.io.*;
import java.util.*;
class Four_Sum
{  static ArrayList<List<Integer>> FourSum(int nums[], int target)
    {  ArrayList<List<Integer>> ans=new ArrayList<>();
        
        if(nums==null||nums.length==0)
        return ans;
        Arrays.sort(nums); // sort the array
        int n=nums.length;
      
        
        for(int i=0;i<n;i++)
        { for(int j=i+1; j<n;j++)
            { int left =j+1;
                int right=n-1;
              int temp_target=target-nums[i]-nums[j]; // sum that we need to find using the two sum technique  
                while(left<right)
                { int curr_two_sum=nums[left]+nums[right];
                     if(curr_two_sum<temp_target)
                       left++;
                     else if(curr_two_sum>temp_target)
                       right--;
                       else
                       { ArrayList<Integer> quad=new ArrayList<>();
                           quad.add(nums[i]);
                           quad.add(nums[j]);
                           quad.add(nums[left]);
                           quad.add(nums[right]);
                           ans.add(quad);
                           
                           while(left<right && nums[left]==quad.get(2)) // skip duplicates
                            left++;
                            
                            while (left< right && nums[right]==quad.get(3)) // skip duplicates
                              right--;
                        }
                }
                while(j+1<n && nums[j]==nums[j+1]) // skip duplicates
                 j++;
            }
             while(i+1<n && nums[i]==nums[i+1]) // skip duplicates
                 i++;
        }
        return ans;
    }
    public static void main(String args[])
    { int nums[]={1,0,-1,0,-2,2};
       int target =0;
       System.out.println(FourSum(nums,target));
    }
}