#include <iostream>

using namespace std;
int treppe( int stufe );
    int stufen;
    char* pointer;
    int counte;
    int moeglichkeiten;
int main( )
{
    // Eingabe:
    cout << "Treppenstufen: ";
    cin >> stufen;
    treppe( stufen );
    cout << "Moeglichkeiten: " << moeglichkeiten;
    delete [] pointer;
    return 0;
}
int treppe( int stufe ) {
    counte++;
    if ( stufe == stufen ) { // Am Anfang wird der char array für die lösung erstellt
    pointer = new char[stufen];
    }
    if ( stufe-2>-1 ) { // Wenn die stufenanzahl -2 nicht ins minus geht rekursion
        pointer[counte] = '2';
        counte = treppe(stufe-2); 
    }
    if ( stufe-1>-1 ) { // Wenn die Stufenzahl -1 nicht ins minus geht: rekursion
        pointer[counte] = '1';
        counte = treppe(stufe-1);
    }
    if ( stufe < 1 ) { // Wenn eine Lösung gefunden wurde ausgeben.
        for( int i=1; i < counte; i++) {
            cout << pointer[i] << " ";
        }
        cout << endl;
        moeglichkeiten++;
    }
        return counte-1; // Einen Schritt zurück gehen
}