Se citeste un numar natural n. Generati, folosind metoda Backtracking, toate deranjamentele multimii {1,2,...,n}, adica toate permutarile in care niciun element nu ramane pe pozitia sa initiala (a[i] != i pentru orice pozitie i de la 1 la n), in ordine lexicografica.
- Date de intrare
- Se citeste numarul natural n.
- Date de iesire
- Se afiseaza toate deranjamentele multimii {1,...,n}, cate unul pe linie, in ordine lexicografica, cu elementele separate prin spatiu. Pentru n=1 nu exista niciun deranjament, deci nu se afiseaza nimic.
- Restrictii
- 1 <= n <= 9
Exemple
Exemplul 1
Intrare
1
Iesire
Exemplul 2
Intrare
2
Iesire
2 1