Se citeste un numar natural n. Generati, folosind metoda Backtracking, toate partitiile multimii {1,2,...,n}, adica toate modurile de a imparti multimea in submultimi nevide, disjuncte doua cate doua, a caror reuniune este multimea intreaga.
- Date de intrare
- Se citeste numarul natural n.
- Date de iesire
- Se afiseaza toate partitiile multimii {1,...,n}, cate una pe linie. Fiecare partitie se afiseaza ca lista submultimilor ei (elementele fiecarei submultimi separate prin spatiu), submultimile fiind separate intre ele prin ' | '.
- Restrictii
- 1 <= n <= 8
Exemple
Exemplul 1
Intrare
1
Iesire
1
Exemplul 2
Intrare
2
Iesire
1 2 1 | 2