# 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

### Young Tableau problem - Cormen

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

A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…

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

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

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

### Container with Most Water - Leet Code Solution

Problem Statement Given n non-negative integers a1, a2, …, an , where each…

### Longest Palindrome Substring - Leet Code Solution

Problem Statement Given a string s, find the longest palindromic substring in s…

## Latest Posts

### Python SMTP Email Code - How to Send HTML Email from Python Code with Authentication at SMTP Server

Introduction This post has the complete code to send email through smtp server…

### Python SMTP Email Code - Sender Address Rejected - Not Owned By User

Introduction In a normal email sending code from python, I’m getting following…

### Nodejs with MongoDB - Number of Opened Connections Keep on Increasing with Mongoose Library

Introduction In one of my app, I was using to talk to . I have used some event…

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…