# include < iostream >
using namespace std ;
int n;
int nr[ 100 ]; // vectorul în care construim numărul
void init ( int k) {
nr[k] = -1 ;
}
int succesor ( int k) {
nr[k]++;
return 1 ;
}
int valid ( int k) {
int nr_0 = 0 , nr_1 = 0 ;
for ( int i = 0 ; i <= k; i++) {
if (nr[i] == 0 ) {
nr_0++;
} else {
nr_1++;
}
}
if (k == n -1 && nr_0 != nr_1) {
return 0 ; // ultima cifră trebuie să fie diferită de celelalte cifre
}
if (nr_0 > n/ 2 || nr_1 > n/ 2 ) {
return 0 ; // numărul nu are același număr de cifre de 0 și 1 ca n
}
return 1 ;
}
int solutie ( int k) {
if (k == n -1 ) { // am generat un număr cu n cifre
int nr_0 = 0 , nr_1 = 0 ;
for ( int i = 0 ; i < n; i++) {
if (nr[i] == 0 ) {
nr_0++;
} else {
nr_1++;
}
}
if (nr_0 == nr_1 && nr[ 0 ] == 1 ) { // numărul are același număr de cifre de 0 și 1 și începe cu 1
return 1 ;
}
}
return 0 ;
}
void tipar () {
for ( int i = 0 ; i < n; i++) {
cout << nr[i];
}
cout << endl ;
}
void bt ( int k) {
init (k);
while (succesor(k)) {
if (valid(k)) {
if ( solutie (k)) {
tipar();
} else {
bt (k+ 1 );
}
}
}
}
int main () {
cout << "Introduceți numărul n: " ;
cin >> n;
bt ( 0 ); // apelul funcției de backtracking cu k=0
return 0 ;
}