B3622 枚举子集（递归实现指数型枚举）← 经典 DFS 写法

【题目来源】
https://www.luogu.com.cn/problem/B3622

【题目描述】
今有 n 位同学，可以从中选出任意名同学参加合唱。
请输出所有可能的选择方案。

【输入格式】
仅一行，一个正整数 n。

【输出格式】
若干行，每行表示一个选择方案。
每一种选择方案用一个字符串表示，其中第 i 位为 Y 则表示第 i 名同学参加合唱；为 N 则表示不参加。
需要以字典序输出答案。

【输入样例】
3

【输出样例】
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY

【数据范围】
对于 100% 的数据，保证 1≤n≤10。

【算法分析】
● DFS 算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/118736059

void dfs(int step) { 判断边界 { 输出解 } 尝试每一种可能 { 满足check条件{ 标记 继续下一步：dfs(step+1) 恢复初始状态（回溯的时候要用到） } } }

● dfs(pos)：从第 pos 位开始枚举选择，递归生成第 pos 位到第 n 位的所有 0/1 组合。

【算法代码】

#include<bits/stdc++.h> using namespace std; const int N=15; int a[N]; int n; void dfs(int pos) { if(pos==n+1) { for(int i=1; i<=n; i++) { if(a[i]) cout<<"Y"; else cout<<"N"; } cout<<endl; return; } a[pos]=0; dfs(pos+1); a[pos]=1; dfs(pos+1); } int main() { cin>>n; dfs(1); return 0; } /* in: 3 out: NNN NNY NYN NYY YNN YNY YYN YYY */

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160587719

​