Four Sum - Leet Code Solution

November 17, 2020

Problem Statement
Solution
Code
Complexity

Problem Statement

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

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

Input: nums = [], target = 0
Output: []

Solution

Lets take help of our two-sum problem.

Code

private List<List<Integer>> twoSum(int[] nums, int target, int start) {
  List<List<Integer>> res = new ArrayList<>();
  int l = start;
  int r = nums.length-1;
  while (l < r) {
    
    /**
      * second conditions are for avoiding duplicates.
      */
    
    if (nums[l] + nums[r] < target || (l > start && nums[l-1] == nums[l])) {
      l++;
    }
    else if (nums[l] + nums[r] > target || (r < nums.length-1 && nums[r] == nums[r+1])) {
      r--;
    }
    else {
      List<Integer> t = new ArrayList<>();
      t.add(nums[l]);
      t.add(nums[r]);
      res.add(t);
      l++;
      r--;
    }
  }
  
  return res;
}

// -2 -1 0 0 1 2
private List<List<Integer>> helper(int[] nums, int target, int startIndex, int k) {
  List<List<Integer>> res = new ArrayList<>();
  
  if (startIndex >= nums.length || nums[startIndex] * k > target || target > nums[nums.length - 1] * k) {
    return res;
  }
  else if (k == 2) {
    return twoSum(nums, target, startIndex);
  }
  else {
    for (int i=startIndex; i<nums.length; i++) {
      //This condition is to avoid duplicates
      if (i == startIndex || nums[i] != nums[i-1]) {
        List<List<Integer>> res2 = helper(nums, target-nums[i], i+1, k-1);
        for (List<Integer> t : res2) {
          List<Integer> newRes = new ArrayList<>();
          newRes.add(nums[i]);
          newRes.addAll(t);
          
          res.add(newRes);
        }
      }
    }
  }
  
  return res;
}

public List<List<Integer>> fourSum(int[] nums, int target) {
  //sorting will help in avoiding duplicates in easy manner
  Arrays.sort(nums);
  
  return helper(nums, target, 0, 4);
}