Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

Leetcode 4Sum problem solution

YASH PAL, 31 July 2024

In this Leetcode 4Sum problem solution we have 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:

  1. 0 <= a, b, c, d < n
  2. a, b, c, and d are distinct.
  3. nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Leetcode 4Sum problem solution

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;
}

coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
©2025 Programming101 | WordPress Theme by SuperbThemes