# How to solve "Four Sum" ZCO17 Problem

I am unable to solve

## this problem

under given constraints. Can anyone can provide hints/ideas/or solutions on how to solve this?

## Problem Statement:

In this problem you are given a sequence of N positive integers S1,S[2], … S[N].
In addition you are given an integer T, and your aim is to find the number of quadruples (i, j, k, l),
such that 1 <= i < j < k < l <= N, and S[i] + S[j] + S[k] + S[l] = T.
That is, the number of ways of picking four numbers from the sequence summing up to T.

## Contraints:

1 <= N <= 5000

1 <= T <= 1000000

1 <= S[i] <= 1000000000 , for all i.

You can find all combinations(I hope you have knowledge of permutations and combinations) of the array having four elements.

If the sum of the array is T you can increment counter, which will give the answer after you have gone through all possible combinations.

A way to optimize this approach would be to sort the array before finding the combinations, by this we can stop making combinations for a particular case if the sum exceeds T.

Since, the constraints are not to big I think this program won’t give TLE.

I think you can use hashing(map/set/array) + O(n^2) loop to find all the combinations of sum
PS: I used hashing with array ( because it’s fastest)

1 Like

Has anyone been able to solve this? I wrote a brute force but even the brute force is giving wrong answers.

I was able to solve this problem for 60pts using the brute force algorithm that I had told about earlier, solution link: https://www.codechef.com/viewsolution/21727004

By the way are you giving ZCO ?

I will let you know after trying this approach…

This should give TLE I think if I understood what you meant

6222 submissions on 1st one… 7 submissions in this one… can’t be that simple XD

one more counter argument is ans can be 5000C4 at most… if you are doing ans++ for every sum=T then its definitely TLE…

exactly… this has to give TLE…

ans can be 5000C4 at most… if you are doing ans++ for every sum=T then its definitely TLE…

#### HERE is my accepted solution…

#you need hashing+n^2 loop to solve this…

### I have commented few things in my solution… you can have a look

mine gives AC… have a look…

#quick explanation :