In this post, we are going to solve the 18. 4Sum problem of Leetcode. This problem 18. 4Sum is a Leetcode medium level problem. Let’s see code, 18. 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 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

Now, let’s see the code of 18. 4Sum – Leetcode Solution.

4Sum – Leetcode Solution

18. 4Sum – Solution in Java

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
      int n = nums.length;
      Arrays.sort(nums);
      List<List<Integer>> result = new ArrayList<>();
      for (int i = 0; i < n; ++i) {
        if (i > 0 && nums[i - 1] == nums[i]) continue;
        threeSum(nums, i + 1, n - 1, target - nums[i], result);
      }
      return result;
    }
  
    private void threeSum(int[] nums, int lo, int hi, int target, List<List<Integer>> result) {
      int n = nums.length;
      int subLen = hi - lo + 1;
      for (int i = lo; i <= hi; ++i) {
        if (i > lo && nums[i] == nums[i - 1]) continue;  
        int j = i + 1, k = hi;
        int t = target - nums[i];
        while (j < k) { 
          if (nums[j] + nums[k] < t) {
            ++j;
          } else if (nums[j] + nums[k] > t) {
            --k;
          } else { 
            result.add(Arrays.asList(nums[lo - 1], nums[i], nums[j], nums[k]));
            ++j;
            --k;
            while (j < k && nums[j] == nums[j - 1]) j++;  
            while (j < k && nums[k] == nums[k + 1]) k--;  
          }
        }
    }
}
}

18. 4Sum – Solution in C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> total;
        int n = nums.size();
        if(n<4)  return total;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
            for(int j=i+1;j<n-2;j++)
            {
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                int left=j+1,right=n-1;
                while(left<right){
                    int sum=nums[left]+nums[right]+nums[i]+nums[j];
                    if(sum<target) left++;
                    else if(sum>target) right--;
                    else{
                        total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        do{left++;}while(nums[left]==nums[left-1]&&left<right);
                        do{right--;}while(nums[right]==nums[right+1]&&left<right);
                    }
                }
            }
        }
        return total;
    }
};

18. 4Sum – Solution in Python

class Solution:
    def fourSum(self, num, target):
        two_sum = collections.defaultdict(list)
        res = set()
        for (n1, i1), (n2, i2) in itertools.combinations(enumerate(num), 2):
            two_sum[i1+i2].append({n1, n2})
        for t in list(two_sum.keys()):
            if not two_sum[target-t]:
                continue
            for pair1 in two_sum[t]:
                for pair2 in two_sum[target-t]:
                    if pair1.isdisjoint(pair2):
                        res.add(tuple(sorted(num[i] for i in pair1 | pair2)))
            del two_sum[t]
        return [list(r) for r in res]

Note: This problem 18. 4Sum is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.