// 这段代码通过深度优先搜索的方式，递归地生成集合的所有子集，并输出每个子集。
#include <cstdio>
#include <cstring>  
#include <iostream>
#include <algorithm>
using namespace std;
// 定义常量大小
const int N=20;

int n;
//布尔数组 st[]，用来记录集合中的元素是否被选中。
bool st[N]; //判断选还是不选

// 参数 u 表示当前需要考虑是否选择的元素位置。
void DFS(int u){ //第几层就是筛选第几个数字

    // 当 u 超过集合大小 n 时，说明已经考虑完了所有元素，此时输出被选中的数。
    if(u>n){ //不可以有等号，如果有等号会少一层递归，即最后一层无法递归 

        for(int i=1;i<=n;i++)//从1到n选择
        if(st[i])  //把选择的数打印出来
            cout<<i<<" ";
        cout<<endl;//输出换行
        return ;
    }
    //如果当前位置 u 没有超过集合大小 n，则进行两种选择：选择当前元素和不选择当前元素，分别进行递归调用。
    else {
        // st[u] = true; DFS(u + 1);: 选择当前元素，将 st[u] 设置为 true，并递归调用下一层，即 u + 1。
        st[u]=true;//选这个数字
        DFS(u+1);
        // st[u] = false; DFS(u + 1);: 不选择当前元素，将 st[u] 设置为 false，并递归调用下一层，即 u + 1。
        st[u]=false;//不选这个数字
        DFS(u+1);
    }
}
int main() {
    cin>>n;
    // DFS(1);: 调用深度优先搜索函数，从第一个元素开始选择。
    DFS(1);  //从1开始选择，到n结束，所以不能从0开始；
    return 0;
}