Se citeste un numar natural nenul n. Determinati, folosind metoda Backtracking, numarul de partitii distincte ale lui n (numarul de moduri de a scrie n ca suma de numere naturale nenule, fara a tine cont de ordinea termenilor).
- Date de intrare
- Se citeste numarul natural nenul n.
- Date de iesire
- Se afiseaza un singur numar: numarul de partitii ale lui n.
- Restrictii
- 1 <= n <= 40
Exemple
Exemplul 1
Intrare
1
Iesire
1
Exemplul 2
Intrare
4
Iesire
5