Skip to content
Programming101
Programmingoneonone

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
Programmingoneonone

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

Topics we are covering

Toggle
  • Problem solution in Python.
  • Problem solution in Java.
  • Problem solution in C++.
  • Problem solution in C.

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 solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • 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
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes