第十六届蓝桥杯康复训练--1
题目链接:92. 递归实现指数型枚举 - AcWing题库
思路:因为题目要求必须升序输出,所以在递归遍历的时候从1开始就好,然后遍历过的变量打个标记,避免重复遍历,到n个就输出路径上所有的数,需要注意是,题目中允许任取0个数,也就是说输出存在空行
代码:
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n;
bool vis[N];
vector<int> paths;
map<vector<int>,bool> mp;
void func(int u,int num){
if(paths.size()==num){
for(auto it:paths){
cout<<it<<" ";
}cout<<endl;
return;
}
for(int i=u;i<=n;i++){
if(vis[i])continue;
paths.push_back(i);
vis[i]=true;
func(i,num);
paths.pop_back();
vis[i]=false;
}
}
void solve(){
cin>>n;
for(int i=0;i<=n;i++){
// 任取多少个数
func(1,i);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}