Reducing time complexity for finding all possible triplets in an array? [closed]

So I have an array sized N. It is sure that array has all distinct elements.

I need to find sum of all possible triplets in that array and for that i need to find all possible triplets.

What i did: looping through array with three nested $for$ loops but that gives O(n^3).

I want to optimise the algorithm as n is very large(upto 10000)

Eg: Array==> {1,2,3,4,5}

Possible triplets: {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5}

• What do you mean by "sum of all possible triplets"? The sum of the elements in each triplet over all triplets? Jan 21 '17 at 15:19
• @quicksort Yes.. Jan 21 '17 at 15:58
• The beginners mistake: You found an obvious way to get the result, and there is a step in that obvious method taking O (n^3). You try to find a way to do that part faster, instead of stepping back and realising that there is no need actually to solve that problem. Jan 21 '17 at 16:59
• @gnasher729 Not quite a beginners mistake but a reading mistake , I misread the question quicksort asked above , hence he gave the solution according to it which was pretty obvious.. Jan 21 '17 at 18:13
• Could you clarify what the output is supposed to be? You've commented on an answer that it's not calculating the right thing but the answer looks like a perfectly reasonable interpretation of what you've written. Jan 21 '17 at 19:08

Finding all the triplets is in fact useless. Let $|A| = n$. Observe that each $a \in A$ appears in exactly $\binom{n-1}{2}$ triplets.

Therefore, the requested sum is just:

$$\sum_{a \in A} \binom{n-1}{2}a = \binom{n-1}{2} \sum_{a \in A} a$$

• ... and calculated in O (n). Jan 21 '17 at 16:56
• Hey, I think i misread you question above , I want the sum of every triplet individually like {1,2,3}=1+2+3=6 {1,2,4}=1+2+4=7 Jan 21 '17 at 18:11
• @AyushGoyal, I'm officially confused. Can you please state your problem formally? What output would you like exactly? If you need even just one symbol per triplet, then you're bound to a solution in $\Omega(n^3)$, as there are $\binom{n}{3} \in \Theta(n^3)$ triplets. Jan 21 '17 at 18:24

Let n be the length of the array A

for (i = 0, i < n - 2, i++)
for (j = i + 1, j < n - 1, j++)
for (k = j + 1, k < n - 0, k++)
sum += i + j + k


You are iterating each result exactly once. I don't think you are going to do better on the iteration. It is O($\binom{n}{3}$). You can get number from combination.

If you look at as every element will appear with every other pair (2) from a set of n-1 then combin(n-1,2) for each element. Just sum the array and multiply by that number.

$\sum_{a \in A} \binom{n-1}{2}$