Rezolvare PBinfo #3790

Se dă șirul a1, a2, …, an de numere naturale nenule distincte. Vrem să alegem trei submulțimi X, Y și Z cu proprietățile:

• submulțimile sunt nevide
• orice element din șir aparține cel mult unei submulțimi
• cele trei submulțimi au suma elementelor identică

De exemplu, dacă a = (1,2,3,4,5,6), atunci putem alege submulțimile: X={1,4}, Y={2,3}, Z={5}. Se observă că au toate suma elementelor egală cu 5 și că 6 nu apare în niciuna din submulțimi. O altă alegere este X={1,6}, Y={2,5}, Z={3,4} și în acest caz toate submulțimile au suma 7 și toate elementele șirului aparțin uneia dintre submulțimi.

Reținem faptul că ordinea elementelor într-o submulțime nu contează, deci X={1,4} este totuna cu X={4,1}. De asemenea, ordinea celor trei submulțimi nu contează, adică de exemplu X={1,4}, Y={2,3}, Z={5} înseamnă același triplet cu X={2,3}, Y={1,4}, Z={5}

Cerința

Să se determine numărul tripletelor de submulțimi care îndeplinesc proprietățile.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n cele numere naturale a1, a2, …, an, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul tripletelor de submulțimi.

Restricții și precizări

• 3 ≤ n ≤ 10
• cele n numere din șir vor fi nenule, distincte două câte două și mai mici decât 100

Exemplul 1:

Intrare

6
1 2 3 4 5 6

Ieșire

3

Explicație

Cele trei triplete sunt:

• {1,4} {2,3} {5}
• {1,5} {6} {2,4}
• {1,6} {2,5} {3,4}

Exemplul 2:

Intrare

5
1 2 3 4 7

Ieșire

0