链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

从 1∼n1\sim n1∼n这 n (n≤16)(n \leq 16)(n≤16) 个整数中随机选取任意多个，输出所有可能的选择方案。

输入描述:

一个整数n。

输出描述:

每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(i>>j&1)
            {
                cout<<j+1<<' ';
            }
        }
        cout<<endl;
    }
	return 0;
}

这个题就是枚举，可以结合二进制的特点来看。

每一个数的存在与否就看成0和1，那么就有2的n次方种。

接着就是要找二进制数中为1的输出j+1就可以。

另外还可以用dfs来做。

#include<bits/stdc++.h>
using namespace std;
int n;
bool st[100]={false};
void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++)
            if(st[i])
               cout<<i<<" ";
            cout<<endl;
            return;
    }
    st[u]=true;
    dfs(u+1);//选择当前分支

    st[u]=false;
    dfs(u+1);//不选当前分支

}

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

另外，还有一个拓展：

题目描述

把 1∼n这 n(n<10)个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入描述:
一个整数n。
输出描述:
按照从小到大的顺序输出所有方案，每行1个。 首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

示例1

输入
3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

void dfs(int u){
   if(u==n+1){                 //递归边界，已经处理完排列的1~n位
       for(int i=1;i<=n;i++)
           cout<<P[i]<<" ";   //输出当前排列
       cout<<endl;
       return ;
   }
   for(int i=1;i<=n;i++){    //枚举1~n，试图将x填入P[u]中，
       if(st[i]==false){     //如果不在P[0]~P[u-1]中，
           P[u]=i;           //将P的第u位为i，即将i加入到当前排列
           st[i]=true;       //记i已经在u号位
           dfs(u+1);       //处理排列载=在第u+1号位
           st[i]=false;       //已经处理完P[u]为i的子问题，还原
       }
   }
}