当前位置：首页 > article >正文

第十六届蓝桥杯康复训练--1

article 2025/3/18 0:51:00

题目链接：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;
}