# Four Sum - Leet Code Solution

November 17, 2020

## 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<>();
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<>();

}
}
}
}

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);
}
``````

O(n^2)

## Similar Posts

### Convert String to Integer - atoi - Leet Code Solution

Problem Statement Implement atoi which converts a string to an integer…

### Check whether number is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

### Young Tableau problem - Cormen

Young Tableau A a X b matrix is Young Tableau if all rows(from left to right…

### Counting Sort Algorithm

Counting sort runs on relatively smaller set of input. Counting sort calculates…

### Validate Sudoku - Leet Code Solution

Problem Statement Determine if a 9x9 Sudoku board is valid. Only the filled…

### Find if Array contains Duplicate Number - Leet Code Solution

Problem Statement Given an array of integers, find if the array contains any…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…