# include < iostream >
# include < cstring >
using namespace std ;
typedef int stiva[ 100 ];
int n; // numarul de cifre ale numerelor
int cifre[ 100 ]; // vectorul de cifre al numerelor
stiva st; // stiva de selectie
// initializare stiva
void init ( int k) {
st[k] = 0 ;
}
// functia de generare a succesorilor
int succesor ( int k) {
if (st[k] < 4 ) { // 0 este deja inclus in cifrele formatei
st[k]++;
return 1 ;
} else {
return 0 ;
}
}
// functia de verificare a solutiei
int solutie ( int k) {
return k == n;
}
// functia de verificare a validitatii solutiei partiale
int valid ( int k) {
if (k == 1 ) {
return 1 ; // prima cifra poate fi oricare
} else {
return cifre[k -1 ] >= cifre[k]; // cifra curenta trebuie sa fie mai mica sau egala cu cea anterioara
}
}
// functia de afisare a solutiei
void tipar () {
for ( int i = n; i >= 1 ; i--) {
cout << cifre[i];
}
cout << endl ;
}
// functia de backtracking
void bt ( int k) {
init (k);
while ( succesor (k)) {
cifre[k] = st[k] * 2 ; // convertim selectia in cifra corespunzatoare
if ( valid (k)) {
if ( solutie (k)) {
tipar ();
} else {
bt (k+ 1 );
}
}
}
}
int main () {
// citirea datelor de intrare
cout << " Introduceti numarul de cifre ale numerelor: " ;
cin >> n;
// apelul functiei de backtracking
bt ( 1 );
return 0 ;
}