How can I efficiently find the number of quadruples in an array which sum up to k?

Question

Example : $[4,2,2,2,2], k=8$

Answer : $- (1)$

As only $1$ quadruple $(2+2+2+2=8)$ exists whose sum is '$8$'.

I know the brute-force $O(n^4)$ algorithm , I even know an $O(n^2\cdot log(n))$ algorithm , but it unfortunately does not work with duplicate elements.

Any better-efficient way to solve it ?

Thanks!

Answer 1

1. Let $a=\frac{k}{4}$. Then go through your array and select all items with value $a$. If $n$ is the number of such items, there are $\binom{n}{4}$ ways of making a quadruple.

2. You can also do it with a MIP : use binary variables $x_i$ that take value $1$ if and only if the element with index $i$ and value $v_i$ is in the quadruple. Define a dummy objective : $$ \max 0 $$ subject to

   • You want quadruples only ($4$ elements) : $$ \sum_{i=1}^n x_i = 4 $$
   • The $4$ elements must have the same value : $$ x_i v_i = x_j v_j \quad \forall i\neq j$$
   • The $4$ elements must sum up to $k$ : $$\sum_{i=1}^n x_i v_i =k$$

Once you have a solution, resolve the problem with the following additional constraint $$ \sum_{i\in B } x_i + \sum_{i\in N } x_i \le 3 $$ where $B$ is the set of variables of the first solution with value $1$, and $N$ the ones will value $0$. This will exclude the first solution. Iterate until the problem is no longer feasible, and you have all your quadruples.

Of course the complexity is not polynomial, but if your arrays are not too big it should be efficient.