1. 选择的分支
2. 不选择的分支

#include <iostream>
using namespace std;

const int N = 1e1 + 6;

int n;
int st[N];

void dfs(int u)
{
    if(u > n) //! 终止条件
    {
        for(int i = 1; i <= n; i++)
            if(st[i] == 1) printf("%d ", i);
        puts("");
        return;
    }

    st[u] = 1; //! 选择的分支
    dfs(u + 1);
    st[u] = 0;

    st[u] = 2; //! 不选择的分支
    dfs(u + 1);
    st[u] = 0;
}

int main(void)
{
    scanf("%d", &n);

    dfs(1);

    return 0;
}

/*
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>


using namespace std;

const int N = 16;

int n;
int st[N];  // 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它
vector<vector<int>> ways;

void dfs(int u)
{
    if (u > n)
    {
        vector<int> way;
        for (int i = 1; i <= n; i ++ )  // 记录方案
            if (st[i] == 1)
                way.push_back(i);
        ways.push_back(way);
        return;
    }

    st[u] = 2;
    dfs(u + 1);     // 第一个分支：不选
    st[u] = 0;  // 恢复现场

    st[u] = 1;
    dfs(u + 1);     // 第二个分支：选
    st[u] = 0;  // 恢复现场
}

int main()
{
    cin >> n;

    dfs(1);

    for (int i = 0; i < ways.size(); i ++ )
    {
        for (int j = 0; j < ways[i].size(); j ++ ) printf("%d ", ways[i][j]);
        puts("");
    }

    return 0;
}
*/