GeetCode Hub

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

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<List<Integer>>(); int len = nums.length; if(len < 4){ return res; } Arrays.sort(nums); return kSum(nums, 0, 4, target); } private List<List<Integer>> kSum(int[] nums, int start, int k, int target){ List<List<Integer>> res = new ArrayList<List<Integer>>(); if(k==2){ return twoSum(nums, start, target); } else{ for(int i=start;i<nums.length-k+1;i++){ List<List<Integer>> kSumList = kSum(nums, i+1, k-1, target-nums[i]); if(kSumList != null && kSumList.size() > 0){ for(List<Integer> curr : kSumList){ curr.add(0, nums[i]); } res.addAll(kSumList); } while(i<nums.length-1 && nums[i] == nums[i+1]){ i++; } } return res; } } private List<List<Integer>> twoSum(int[] nums, int start, int target){ int i=start; int j= nums.length-1; List<List<Integer>> res = new ArrayList<List<Integer>>(); while(i<j){ int currSum = nums[i]+nums[j]; if(currSum < target){ i++; } else if(currSum > target){ j--; } else{ List<Integer> ans = new ArrayList<Integer>(); ans.add(nums[i]); ans.add(nums[j]); res.add(ans); while(i<j && nums[i] == nums[i+1]){ i++; } while(i<j && nums[j] == nums[j-1]){ j--; } i++; j--; } } return res; } }

The main concept of this question is to re-use the existing solved results of 2-sum problems and 3-sum problems, which we can directly append with the current result.

Time Complexity: O(n^3)

Space Complexity:O(n)  // for storing the results.

Easy
Two Sum
Medium
3Sum
Medium
4Sum II