#include<stdio.h>
#include<assert.h>

#define MAX_N 100


void printSol(int pos_write, char* prefix) {
  int i;
	for(i = 0; i < pos_write; i++)	    printf("%c", prefix[i]);
  printf("\n");
}


void listaPiastrellature(int n, int pos_write, char* prefix) {
/*
   assume che in prefix[0, ..., pos_write-1 ] sia presente
   un prefisso di piastrellatura possibile e che rimanga ancora
   da coprire un bagno residuo di lunghezza n. 
*/
  assert( n >= 0 );

  if(n==0) { // la superficie piastrellabile e' finita: la stampo e termino
	printSol(pos_write, prefix); 
	return; 
	}
// se c'e' ancora superficie disponibile => piastrella 1 e continuo ricorsivamente
prefix[pos_write] = '1';
listaPiastrellature(n-1, pos_write +1, prefix);
// se c'e' spazio per 2 piastrelle => piastrella 2 e continuo ricorsivamente
  if(n>=2) {
     prefix[pos_write] = '2';
     listaPiastrellature(n-2, pos_write +1, prefix);
  }
}

int main() {
	char prefix[MAX_N];
  printf("Inserire numero piastrelle: ");
  int n; scanf("%d", &n); assert( n <= MAX_N );
  listaPiastrellature(n, 0, prefix);
}