submultimi

#include <bits/stdc++.h>
#define dim 100
using namespace std;

///ifstream f("permutari.in");
///ofstream g("permutari.out");

int sol[dim],n,nr=0,p;

void tipar(int k)
{
    cout<<"{ ";
    for(int i=1;i<=k;i++){
        cout<<sol[i]<<" ";
    }
    cout<<"}"<<endl;
}

int valid(int k)
{
    for(int i=1;i<=k-1;i++){
        if(sol[i]>=sol[k])
            return 0;
    }
    return 1;
}

int succesor(int k)
{
    if(sol[k]<n){
        sol[k]++;
        return 1;
    }
    return 0;
}

void citire()
{
    cin>>n;   ///C(n,p);
}

void backtr(int k)
{
    if (k>1)
        tipar(k-1);
   /// else
    {
            sol[k]=0;
            while(succesor(k)){
                if(valid(k)){
                    backtr(k+1);
                }
            }
    }
}
int main()
{
    citire();
    cout<<"{}"<<endl;
    backtr(1);
    return 0;
}