一. 题目

二. 理论

• 分成递归树的每层，分为>=2层情况去枚举即可。

三. 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=20;

int n;

class Search
{
public:
    bool st[N];//true表示当前数选，否则不选
public:
    void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    Search()
    {
        initIO();
        fill(st, st+N, false);
    }

    /**
     * 搜索函数
     * @param u 表示当前在第几层，最开始在第0层，当u==n时，说明到达最后一层
     *          同时u+1也代表某个数
     */
    void dfs(int u)
    {
        if(u==n)
        {
            for(int i=1;i<=n;++i)
                if(st[i])
                    cout<<i<<" ";
            cout<<endl;
            return;
        }

        //选
        st[u+1]=true;
        dfs(u+1);
        st[u+1]= false;//回溯

        dfs(u+1);//不选当前数
    }
}s;

int main()
{
    cin>>n;
    s.dfs(0);
}