题目描述
从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。
1≤n≤15
样例
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
C++ 代码
、#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int st[25];
vector<vector<int > >ways;//储存方案
//1~n 顺序:依次考虑每个数选或不选
void dfs(int u){
if(u>n){
/*
中间输出:
for(int i=1;i<=n;i++)
if(st[i]==1)cout<<i<<" ";
cout<<endl;
*/
//或者储存方案(存在vector中),最后输出:(但时间会比在中间输出要慢很多)
vector<int> way;
for(int i=0;i<=n;i++){
if(st[i]==1)way.push_back(i);//储存方案
}
ways.push_back(way);
return ;
}
st[u]=2;//分支一
dfs(u+1);//不选
st[u]=0;//恢复现场
st[u]=1;//分支二
dfs(u+1);//选
st[u]=0;//恢复现场
return;
}
int main(){
cin>>n;
dfs(1);
for(int i=0;i<ways.size();i++){
for(int j=0;j<ways[i].size();j++)
cout<<ways[i][j]<<" ";//输出方案
cout<<endl;
}
return 0;
}