1.19

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

namespace Algo1_19{
    void run(){
        vector < vector < vector < ll > > > res;
        ll n;
        cin >> n;
        res.push_back({{1}});
        for (ll i=2; i<=n; i++){
            vector < vector < vector < ll > > > tmp;
            for (ll j=0; j<res.size(); j++){
                if (j&1){
                    res[j].push_back({i});
                    tmp.push_back(res[j]);
                    res[j].pop_back();
                    for (ll k=res[j].size()-1; k>-1; k--){
                        res[j][k].push_back(i);
                        tmp.push_back(res[j]);
                        res[j][k].pop_back();
                    }
                }else{
                    for (ll k=0; k<res[j].size(); k++){
                        res[j][k].push_back(i);
                        tmp.push_back(res[j]);
                        res[j][k].pop_back();
                    }
                    res[j].push_back({i});
                    tmp.push_back(res[j]);
                    res[j].pop_back();
                }
            }
            res = tmp;
        }
        for (vector<vector<ll>> &i: res){
            for (vector<ll> &j: i){
                cout << '{';
                for (ll &k: j){
                    cout << k << " }"[k==j.back()];
                }
            }
            cout << '\n';
        }
    }
}