# 4 Sum Leetcode Solution In C, C++, Python And Java

4 Sum LeetCode Solution is an engaging programming challenge that gives you an opportunity to flex your optimization and problem-solving muscles. In this in-depth tutorial, we will cover various approaches to finding the 4 Sum leetcode problem solution along with examples, code, and explanations so you can master the concepts behind this frequently encountered problem.

## Introduction to 4 Sum Leetcode Problem

### Problem Statement

Given an array `nums` of n integers and an integer `target`, are there four 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`.

### Example

``````Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
``````
Plaintext

## Approach & Algorithm

### Explanation:

Before diving into the optimized solution for the 4 Sum leetcode problem, let’s familiarize ourselves with the various techniques that are commonly applied. The most efficient approach for solving this problem combines the sorting algorithm or sorted array and two pointers strategy.

First, sort the array `nums`. Then, iterate through the array using two nested loops (i.e., i and j). For each pair of (i, j), find all pairs (k, l) such that `nums[i] + nums[j] + nums[k] + nums[l] = target` using the two pointers method. Now, to avoid duplicates, skip the elements that are equal to their previous element.

Finally, return the resulting list of quadruplets.

### Pseudocode:

``````1. Sort array nums of n integers
2. For i in 0 to (length of nums - 3):
a. If i > 0 and nums[i] == nums[i - 1], continue to next iteration
b. For j in (i + 1) to (length of nums - 2):
- If j > i + 1 and nums[j] == nums[j - 1], continue to next iteration
- Initialize two pointers: k = j + 1, l = length of nums - 1
- While k < l:
+ Calculate the current_sum = nums[i] + nums[j] + nums[k] + nums[l]
+ If current_sum == target:
* Increment k, while ensuring nums[k] != nums[k - 1] for unique values
* Decrement l, while ensuring nums[l] != nums[l + 1] for unique values
+ Else if current_sum > target, decrement l
+ Else increment k
3. Return the result
``````
Plaintext

### Complexity analysis:

The time complexity of this optimized approach is O(N^3) and space complexity is O(N) for the additional space required to store the resulting quadruplets.

## Detailed 4 Sum LeetCode Solution in C, C++, Python, Java

### 4 Sum Leetcode Solution C

``````#include <stdio.h>
#include <stdlib.h>
int* sort_array(int* nums, int numsSize) {
for (int i = 0; i < numsSize - 1; i++) {
for (int j = 0; j < numsSize - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
return nums;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
// Sort the input array
nums = sort_array(nums, numsSize);
*returnSize = 0;
/* Allocate memory for the result */
int **result = (int**)malloc(numsSize * numsSize * sizeof(int*));
*returnColumnSizes = (int*)calloc(numsSize * numsSize, sizeof(int));
for (int i = 0; i < numsSize - 3; i++) {
// Skip duplicate elements
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < numsSize - 2; j++) {
// Skip duplicate elements
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = numsSize - 1;
while (k < l) {
int current_sum = nums[i] + nums[j] + nums[k] + nums[l];
if (current_sum == target) {
result[*returnSize] = (int*)malloc(4 * sizeof(int));
result[*returnSize][0] = nums[i];
result[*returnSize][1] = nums[j];
result[*returnSize][2] = nums[k];
result[*returnSize][3] = nums[l];
(*returnColumnSizes)[*returnSize] = 4;
(*returnSize)++;
// Skip duplicate elements
while (k < l && nums[k] == nums[k + 1]) k++;
while (k < l && nums[l] == nums[l - 1]) l--;
k++;
l--;
} else if (current_sum > target) {
l--;
} else {
k++;
}
}
}
}
return result;
}
``````
C

### 4 Sum Leetcode Solution C++

``````#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int n = nums.size();
if (n < 4) return result;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = n - 1;
while (k < l) {
int current_sum = nums[i] + nums[j] + nums[k] + nums[l];
if (current_sum == target) {
result.push_back({nums[i], nums[j], nums[k], nums[l]});
while (k < l && nums[k] == nums[k + 1]) k++;
while (k < l && nums[l] == nums[l - 1]) l--;
k++; l--;
} else if (current_sum > target) {
l--;
} else {
k++;
}
}
}
}
return result;
}
};
``````
C++

### 4 Sum Leetcode Solution Python

``````class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
result = []
for i in range(len(nums) - 3):
if i > 0 and nums[i] == nums[i - 1]: continue
for j in range(i + 1, len(nums) - 2):
if j > i + 1 and nums[j] == nums[j - 1]: continue
k, l = j + 1, len(nums) - 1
while k < l:
current_sum = nums[i] + nums[j] + nums[k] + nums[l]
if current_sum == target:
result.append([nums[i], nums[j], nums[k], nums[l]])
while k < l and nums[k] == nums[k + 1]: k += 1
while k < l and nums[l] == nums[l - 1]: l -= 1
k += 1; l -= 1
elif current_sum > target:
l -= 1
else:
k += 1
return result
``````
Python

### 4 Sum Leetcode Solution Java

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = nums.length - 1;
while (k < l) {
int current_sum = nums[i] + nums[j] + nums[k] + nums[l];
if (current_sum == target) {
while (k < l && nums[k] == nums[k + 1]) k++;
while (k < l && nums[l] == nums[l - 1]) l--;
k++; l--;
} else if (current_sum > target) {
l--;
} else {
k++;
}
}
}
}
return result;
}
}``````
Java

## Conclusion

The 4 Sum leetcode solution discussed in this article utilizes an optimized approach involving sorting and two pointers. By learning how to implement the algorithm in various programming languages like CC++Python, and Java, you are now well-equipped to tackle similar problems efficiently. Remember to be mindful of your choice of optimization techniques and handling edge cases to always stay ahead in your programming endeavors. Happy coding!

## Infix To Postfix Converter

Enter Infix Expression: Convert Postfix Expression: Step Stack Action Explanation Here is a table for each step of…

## Data Types in C

Data types are an essential concept in C programming as they determine the nature of data and the…

## How To Find Minimum and Maximum Element in an Array (C, CPP & Python)

Find Minimum and Maximum Element in an Array When working with arrays, it’s common to need to find…