# 4–Sum Problem | Quadruplets with a given sum

By | November 17, 2021

## Problem

The goal is to count all the quadruplets having target sum `S`.

#### Sample Input

`[2, 2, 2, 2, 2]`

`5`

## Approach

Initialize `ans` variable with `0`. Traverse the given array from `0` to `N-3`. For each element `arr``[i]`, traverse the array again from `i+1 `to `N-2` using the variable `j` and do the following:

Find the value of the required sum as (`S – ``arr[i] – arr``[j]`).

Initialize the `ans2` with `0` that will store the count of ordered pairs in the above subarray with sum (`S – ``arr[i] – arr``[j]`).

After finding the `ans2`, update the `ans` by `ans`` / 2`.

### C++ Programming

```#include <iostream>
#include <unordered_map>
using namespace std;

// Function to return the number of
int solve(int a[], int n, int sum)
{

int i, j, k, l;
int ans = 0;

// all possible first elements
for (i = 0; i < n - 3; i++)
{

// all possible second element
for (j = i + 1; j < n - 2; j++)
{

int req = sum - a[i] - a[j];
unordered_map<int, int> mp;

for (k = j + 1; k < n; k++)
mp[a[k]]++;

int ans2 = 0;

for (k = j + 1; k < n; k++)
{
ans2 += mp[req - a[k]];
if (req - a[k] == a[k])
ans2--;
}
ans += ans2 / 2;
}
}
return ans;
}

int main()
{
int arr[] = {2, 2, 2, 2, 2 };

int S = 8;

int N = sizeof(arr) / sizeof(arr[0]);
cout << solve(arr, N, S);
return 0;
}```

Output

`5`

### Python Programming

```def solve(a, n, total):
ans = 0
# All possible first elements
for i in range(n - 3):
# All possible second elements
for j in range(i + 1, n - 2, 1):
req = total - a[i] - a[j]
mp = {}

for k in range(j + 1, n, 1):
mp[a[k]] = mp.get(a[k], 0) + 1

ans2 = 0

for k in range(j + 1, n, 1):
ans2 += mp.get(req - a[k], 0)
if (req - a[k] == a[k]):
ans2 -= 1
ans += ans2 // 2
return ans

arr = [2, 2, 2, 2, 2]
S = 8
N = len(arr)
print(solve(arr, N, S))
```

Output

`5`

### C# Programming

```using System;
using System.Collections.Generic;

class Solution{
static int solve(int []a, int n,int sum)
{
// Initialize variables
int i, j, k;

int ans = 0;

// All possible first elements
for(i = 0; i < n - 3; i++)
{
// All possible second element
for(j = i + 1; j < n - 2; j++)
{
int req = sum - a[i] - a[j];

Dictionary<int,int> mp = new Dictionary<int,int>();

for(k = j + 1; k < n; k++)
if (mp.ContainsKey(a[k]))
{
mp[a[k]]++;
}

else
{
}

int ans2 = 0;

// Calculate number of valid
// 4th elements
for(k = j + 1; k < n; k++)
{
// Update the ans2
if (mp.ContainsKey(req - a[k]))
ans2 += mp[req - a[k]];

if (req - a[k] == a[k])
ans2--;
}
ans += ans2 / 2;
}
}

return ans;
}

public static void Main(String[] args)
{
int []arr = {2, 2, 2, 2, 2};
int S = 8;
int N = arr.Length;
Console.Write(solve(arr, N, S));
}
}
```

Output

`5`

People are also reading:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.