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ției15*26*34*
deoarece1,2,3,2,3,1
este înaintea lui1,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, 2, 3}
{1, 2} U {3}
{1, 3} U {2}
{1} U {2, 3}
{1} U {2} U {3}