4Sum Problem Solution [Leetcode]

4Sum Problem: 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 :

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

4Sum Problem Solution [Leetcode]

Problem Solution In Python

from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []

        def k_sum(nums, k, target, arr, start_idx):
            if k == 2:
                two_sum(nums, arr, k, start_idx, target)
                return
            for i in range(start_idx, len(nums) - k + 1):
                if i > start_idx and nums[i] == nums[i - 1]:
                    continue
                k_sum(nums, k - 1, target - nums[i], arr + [nums[i]], i + 1)

        def two_sum(nums, arr, k, start_idx, target):
            left = start_idx
            right = len(nums) - 1

            while left < right:
                total = nums[left] + nums[right]
                if total == target:
                    res.append(arr + [nums[left], nums[right]])
                    left += 1
                    right -= 1

                    while left < right and nums[left] == nums[left - 1]:
                        left += 1  # skip same element to avoid duplicate quadruplets
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1  # skip same element to avoid duplicate quadruplets
                elif total < target:
                    left += 1
                else:
                    right -= 1

        k_sum(nums, 4, target, [], 0)
        return res

Problem Solution In Java

public List<List<Integer>> fourSum(int[] nums, int target) {
    
    int n = nums.length;
    List<List<Integer>> res = new ArrayList();
    
    for(int i = 0; i < n-3; i++){
        
        for(int j = i+1; j < n-2; j++){
            
            for(int k = j+1; k < n-1; k++){
                
                for(int t = k+1; t < n; t++){
                    
                    if(nums[i]+nums[j]+nums[k]+nums[t] == target){
                        
                        int[] arr = new int[]{nums[i], nums[j], nums[k], nums[t]};
                        Arrays.sort(arr);
                        
                        if(!contains(arr, res)){
                            res.add(Arrays.asList(arr[0], arr[1], arr[2], arr[3]));
                        }                            
                    }
                }
            }                
        }            
    }
    
    return res;
}

boolean contains(int[] arr, List<List<Integer>> res){
    
    for(List<Integer> itr: res){
        if(itr.get(0) == arr[0] && itr.get(1) == arr[1] && itr.get(2) == arr[2] && itr.get(3) == arr[3])
            return true;
    }
    
    return false;
}

Problem Solution In C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        set<vector<int>>ans1;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            for(int j=i+1;j<n-2;j++)
            {
                int left=j+1;
                int right=n-1;
                while(left<right)
                {
                    int sum1=nums[i]+nums[j];
                    int sum2=target-(nums[left]+nums[right]);
                    if(sum2<sum1)
                    {
                        right--;
                    }
                    else if(sum1==sum2)
                    {
                        vector<int>v{nums[i],nums[j],nums[left],nums[right]};
                        ans1.insert(v);
                        left++;
                    }
                    else
                    {
                        left++;
                    }
                }
            }
        }
        vector<vector<int>>ans(ans1.begin(),ans1.end());
        return ans;
    }
};

Problem Solution In C

int cmp(const void *a,const void *b){
    return *(int *)a-*(int *)b;
}
int** fourSum(int* nums, int len, int target, int* returnSize, int** returnColumnSizes){
    if(len<4){
        *returnColumnSizes=NULL;
        *returnSize=0;
        return NULL;
    }
    qsort(nums,len,sizeof(int),cmp);
    int cnt=0;
    int base=8;
    int **ans=malloc(sizeof(int *)*8);
    int sum;
    int l,r;
    for(int i=0;i<len-3;i++){
        if(i>0&&nums[i]==nums[i-1]){
            continue;
        }
        if(nums[i]*4>target){
            break;
        }
        for(int j=i+1;j<len-2;j++){
            if(j>i+1&&nums[j]==nums[j-1]){
                continue;
            }
            if(nums[j]*3+nums[i]>target||nums[len-1]*3+nums[i]<target){
                break;
            }
            l=j+1;
            r=len-1;
            while(l<r){
                sum=nums[i]+nums[j]+nums[l]+nums[r];
                if(sum==target){
                    ans[cnt]=malloc(sizeof(int)*4);
                    ans[cnt][0]=nums[i];
                    ans[cnt][1]=nums[j];
                    ans[cnt][2]=nums[l];
                    ans[cnt][3]=nums[r];
                    cnt++;
                    if(cnt==base){
                        base*=2;
                        ans=realloc(ans,sizeof(int *)*base);
                    }
                    while(l<r&&nums[l]==nums[l+1]){
                        l++;
                    }
                    while(l<r&&nums[r]==nums[r-1]){
                        r--;
                    }
                    l++;
                    r--;
                }
                else if(sum>target){
                    r--;
                }
                else{
                    l++;
                }
            }
        }
    }
    *returnColumnSizes=malloc(sizeof(int)*cnt);
    for(int i=0;i<cnt;i++){
        (*returnColumnSizes)[i]=4;
    }
    *returnSize=cnt;
    return ans;
}