题解1：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=16;
int n;
bool st[N];  // false 不选， true选
void dfs(int u){  // u 代表当前第几位数字
  if(u>n){
    for(int i=1;i<=n;i++){
      if(!st[i]){  // 如果当前位值状态为true，说明选择了当前位置
        cout<<i<<" ";
      }
    }
    cout<<endl;
    return;
  }
  // 递归一条道走到黑
  
  st[u]=true;// 选择当前分支
  dfs(u+1);   
  st[u]=false; // 还原状态
  
  st[u]=false;  //  不选择当前分支
  dfs(u+1);  
  st[u]=true;// 还原状态
}


int main(){
  cin>>n;
  dfs(1);
  return 0;
}

题解2：

//  思路： 1，2，3，4，5，6，7...
//  组合计数问题，每个数有选与不选两种情况
// 2*2*2*2*2...  =2^n 
// 每个方案的长度为n
// 最终个数是n*2^n


// 递归最重要的是顺序，从1到n依次考虑每个数，选或者不选。
// 需要开一个长度为N的数组来记录状态
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N=16;
int n;
int st[N]; //状态数组，记录每个位置，0表示没考虑，1选择，2不选择

void dfs(int u){  // u是判断到了第几位
  // 边界情况，u枚举到最后一位
  if(u > n){
    for(int i=1;i<=n;i++){
      if(st[i]==1){
        cout<<i<<" ";
      }
    }
    cout<<endl;
    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); //传入到当前枚举到第几位，从第1位开始
  return 0;
}