https://www.acwing.com/problem/content/94/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb(i) push_back(i)
#define int long long
#define INF 0x3f3f3f3f
#define oz  998244353
#define endl '\n'
#define N 20
const int mod = 1e9 + 7;

int n;
int st[N]; // 0未考虑 1选 2不选

void dfs(int x) {

    if (x > n) {
        rep(i, 1, n) {
            if (st[i] == 1)cout << i << " ";
        }

        cout << endl;
        return ;
    }

    //不选
    st[x] = 2;
    dfs(x + 1);
    st[x] = 0;

    //选
    st[x] = 1;
    dfs(x + 1);
    st[x] = 0;

}
void solve() {

    cin >> n;

    dfs(1);
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
//  cin >> T;
    while (T --)
        solve();

    return 0;
}