Solução escrita por Caique Paiva
Conhecimento prévio necessário:
Vamos primeiro resolver o seguinte problema primeiro:
Dado um vetor $$A_1, A_2, …, A_N$$, encontre uma dupla $$(i,j)$$ tal que $$A_i+A_j = X$$ e $$i \ne j$$ ou diga que não existe nenhuma.
Para resolver, primeiro ordene o vetor em ordem crescente. Então, coloque um ponteiro no final da lista (Chamado de $$r$$) e outro no começo (Chamado de $$l$$), e faça o seguinte algoritmo:
- Se $$A_l + A_r = X$$, então conseguimos o que queríamos.
- Se $$A_l + A_r > X$$, então, faça $$r–$$, e dai a soma atual de $$A_l + A_r$$ vai diminuir, pois $$A_r < A_{r+1}$$.
- Se $$A_l + A_r < X$$, então, faça $$l++$$, e dai a soma atual de $$A_l + A_r$$ vai aumentar, pois $$A_l < A_{l+1}$$.
Se $$l >= r$$ em algum momento, então paramos o algoritmo. Esse algoritmo funciona pois, se existe uma dupla $$(i, j)$$, então, primeiro que o algoritmo passa por todos os índices do vetor, logo, alguma das duas coisas vai acontecer primeiro, ou $$l = i$$, ou $$r = j$$, então, suponha sem perda de generalidade que o que acontece primeiro é que $$l = i$$, e logo $$r > j$$, pois $$l = i$$ aconteceu primeiro. Portanto, como $$l = i$$, temos que a soma atual é $$A_i + A_r > X$$, então, vamos sempre diminuir o $$r$$ até ele chegar no $$j$$, logo, nós sempre chegamos na dupla desejada, se ela existir.
Esse algoritmo roda em $$O(N)$$.
Vamos resolver o problema original agora.
Primeiro, vamos ordenar o vetor por ordem crescente. Agora, veja que queremos achar uma tripla tal que $$A_i + A_j = X – A_k$$, portanto, vamos variar $$k$$ começando por $$1$$ e indo até $$N$$, e para cada $$k$$, vamos procurar uma dupla $$(i, j)$$ tal que $$A_i + A_j = X – A_k$$, com $$i \neq j, j \neq k, k \neq i$$. Sabemos como fazer isso em $$O(N)$$, então, como fazemos isso para cada $$k$$ entre $$1$$ a $$N$$, conseguimos fazer isso em $$O(N^2)$$.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.