题目:从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

算法一:位运算(最简单)

机理:指数型枚举即每个数都有选或者不选两种可能,我们可以分别用1和0来表示
这样枚举的每种状态就是0和1的一个组合
这种状态恰好可以用二进制数来表示,二进制数每一位也是0和1两种可能

#include<iostream>
#include<cmath>//pow()要用到,此外指数也可以用位运算表示!
using namespace std;

int main()
{
    int n;//枚举数1~n
    cin>>n;
    for(int i=0;i<pow(2,n);i++)
      {
          for(int j=0;j<n;j++)
            if(i>>j&1)//考虑i这个数的二进制数从右往左数下标第j个是不是1
              cout<<j+1<<' ';
          puts("");     
      }
    return 0;
}

算法二:y总经典法

#include <iostream>
using namespace std;

const int N = 16;

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

void dfs(int u)
{
    if (u > n)
    {
        for (int i = 1; i <= n; i ++ )
            if (st[i] == 1)
                printf("%d ", i);
        printf("\n");
        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);
    return 0;
}

算法三:dfs双参

//受小猫爬山启发,双参dfs,在dfs出口处for(int i=1;i<w;i++),i<=w是错误的????
//如上问题原因:第一种情况dfs(w+1,u+1),到u>n出dfs的时候,w是位于ans有效结果最后一位的后面一位的

#include<iostream>
using namespace std;

int ans[16];
int n;
bool st[16];

void dfs(int w,int u)//w:当前到ans第几位,u:当前在考虑哪个数(ans有效下标设成从1开始)
{
    if(u>n) //已经考虑完了n个数
      {
          for(int i=1;i<w;i++) cout<<ans[i]<<' ';
          puts("");
          return;
      }

    //第一种情况,放入ans
    if(!st[u])
      {
          ans[w]=u;
          st[u]=true;
          dfs(w+1,u+1);//ans往后挪一位,考虑下一个数
          ans[w]=0;//可以不写,因为w位会被后来的数字所覆盖
          st[u]=false;
      }

    //第二种情况,不放入ans
    dfs(w,u+1);
}

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