#include<iostream> /// Problema Permutarilor - folosind Backtracking
using namespace std;
int st[20],n,k,p; /// n = nr de elemente din multime; k = nivelul curent din stiva
int as,ok; /// as=1 daca am succesor;  ok=1 daca bucata de solutie curenta este valida
bool succesor(int k) /// verifica daca pe nivelul curent din stiva poate fi incarcata alta valoare (urmatoarea valoare posibila)
{
  if (st[k]<n)
     {
         st[k]++;
         return true;
      }
 return false;
}

bool valid(int k) /// verifica daca "solutia partiala" obtinuta este corecta (in cazul permutarilor se verif. daca elementele sunt diferite intre ele)
{
    for(int i=1;i<k;i++)
       if(st[i]==st[k])
          return false;
    return true;
}

bool final(int k) /// Verifica daca este solutie finala (in cazul permutarilor stiva trebuie sa fie plina pt. a avea o solutie finala)
{
	return (k==n);
}

void tipar() ///Afiseaza solutia
{
   for(int i=1;i<=n;i++)
	cout<<st[i]<<' '; cout<<endl;
}

int main()
{
	cout<<"nr de elemente n=";
	cin>>n;
    k=1;

  while(k>0)
     {
    /*    Urmatoarea secventa do-while, incarca pe nivelul curent din stiva o noua valoare pana in momentul in care
    se obtine o solutie partiala (o bucatica de solutie) corecta.
    Atat timp cat se poate incarca pe nivelul curent o alta valoare si solutia partiala obtinuta nu este corecta se incarca o noua valoare.
    */
      do
         {
           as=succesor(k);
           ok=valid(k);
         } while (as && !ok);

   if (as) ///daca a reusit sa incarce o noua valoare pe nivelul curent din stiva
     if (final(k))  ///daca este solutie finala
          tipar(); /// se afiseaza solutia
         else  /// altfel, daca nu s-a putut incarca o noua valoare pe nivelul curent din stiva (dar solutia partiala e corecta), atunci se urca in stiva
        {
            k++;
            st[k]=0; /// pe nivelul pe care s-a urcat, se pune valoarea 0
         }
    else k--; ///daca nu exista succesor pentru nivelul curent din stiva (pentru varful stivei) atunci se coboara un nivel
     } /// while
	return 0;
}