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
, andd
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]]
Table of Contents
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;
}