#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> subset;

void back(int k) {
    if (k > n) {
        // am construit o submulțime, o afișăm
        cout << "{ ";
        for (int x : subset)
            cout << x << " ";
        cout << "}" << endl;
    } else {
        // includem elementul k
        subset.push_back(k);
        back(k + 1);

        // nu-l includem pe k
        subset.pop_back();
        back(k + 1);
    }
}

int main() {
    cout << "n = ";
    cin >> n;
    back(1);
    return 0;
}