Se citeste un numar natural nenul n. Generati, folosind metoda Backtracking, toate partitiile lui n, adica toate modurile de a scrie n ca suma de numere naturale nenule, fara a tine cont de ordinea termenilor (o valoare poate aparea de mai multe ori in aceeasi partitie). Fiecare partitie se afiseaza cu termenii in ordine descrescatoare, de la cel mai mare la cel mai mic.
- Date de intrare
- Se citeste numarul natural nenul n.
- Date de iesire
- Se afiseaza toate partitiile lui n, cate una pe linie, cu termenii in ordine descrescatoare, separati prin spatiu. Partitiile se afiseaza incepand cu cea care are primul termen cel mai mare (partitia n insusi), in ordinea generata de backtracking descrisa in indicatii.
- Restrictii
- 1 <= n <= 20
Exemple
Exemplul 1
Intrare
1
Iesire
1
Exemplul 2
Intrare
2
Iesire
2 1 1