Cerința

Fie n un număr natural nenul și mulțimea A={1,2,3,...,n}.

Să se afişeze toate partițiile disjuncte ale mulțimii A într-un timp eficient folosind memoria eficient.

Se recomandă rezolvarea problemei cu id: #1330 întâi.

Date de intrare

Fișierul de intrare partitiimultime2.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire partitiimultime2.in va conține partițiile pe câte o linie, iar elementele fiecărei submulțimi se vor scrie fără spațiere si separarea submulțimiilor se va face cu ajutorul caracterului *.

Restricții și precizări

• 1 ≤ n ≤ 11
• Pentru o rezolvare decentă se obțin 40 de puncte.
• Pentru o rezolvare optimizată se obțin 100 de puncte.
• Partițiile determinate se vor afișa în ordine lexicografică a indicelui submulțimii în care se pun elementele. De exemplu soluția 16*24*35* este afișată înaintea soluției 15*26*34* deoarece 1,2,3,2,3,1 este înaintea lui 1,2,3,3,1,2.

Exemplu:

partitiimultime2.in

3

partitiimultime2.out

123*
12*3*
13*2*
1*23*
1*2*3*

Explicație

Partițiile lui A sunt:

1. {1, 2, 3}
2. {1, 2} U {3}
3. {1, 3} U {2}
4. {1} U {2, 3}
5. {1} U {2} U {3}