# 4–Sum Problem | Quadruplets with a given sum

Posted in

Vinay Khatri
Last updated on December 6, 2023

## Problem

The goal is to count all the quadruplets having a 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 the 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`