Finding the Number of Quadruples

Question

In this problem you are given a sequence of N positive integers S[1],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. For example, for S = [3, 1, 1, 2, 5, 10] and T = 20 the answer is 1 since (1,4,5,6) (using 1-based indexing) is the only valid quadruple as S[1] + S[4] + S[5] + S[6] = 3 + 2 + 5 + 10 = 20.

I have been trying hard to find an efficient solution for the above problem but I am unable to come up with any answer. A strategy to approach such problems along with the pseudo code (and necessary explanation) is highly appreciated.

Answer 1

It can be solved in O(N^2 log N) regardless what T is:

1. First create new array of pairs of distinct indexes and store all index pairings.
2. Sort new array by sum value (i.e. pair {1,2} would have value A[1]+A[2] where A is original array)
3. Now problem gets reduced to some variation of 2SUM problem which can easily be solved as described here with some modifications: we also need to check if all 4 indexes are unique

If T is small enough we can also do some knapsack DP to solve in O(NT):