思路：

深度优先搜索

递归每个位置，每个位置有两种状态，选或者不选，因此可以开一个bool数组来记录

代码：

#include<iostream>
using namespace std;

const int N=20;
int n;
bool st[N] //用来记录状态

void dfs(int u)
{
  if(u>n)//如果枚举到第n+1个位置，则说明枚举结束
  {
    for(int i=1;i<=n;i++)
      if(st[i])printf("%d ",i); //如果选择了那个数，就输出
    puts("");
    return;
  }
  st[u]=false; //不选择当前的数
  dfs(u+1); //枚举下一个位置
  st[u]=true; //选择当前的数
  dfs(u+1); //枚举下一个位置
}

int main()
{
  cin>>n;
  dfs(1);//从第1个位置开始
  return 0;
}