【题目来源】
【题目描述】
今有 n 位同学，可以从中选出任意名同学参加合唱。
请输出所有可能的选择方案。
【输入格式】
仅一行，一个正整数 n。
【输出格式】
若干行，每行表示一个选择方案。
每一种选择方案用一个字符串表示，其中第 i 位为 Y 则表示第 i 名同学参加合唱；为 N 则表示不参加。
需要以字典序输出答案。
【输入样例】
3
【输出样例】
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY
【数据范围】
对于 100% 的数据，保证 1≤n≤10。
【算法分析】
● DFS 算法模板：
void dfs(int step) {判断边界 {输出解}尝试每一种可能 {满足check条件{标记继续下一步：dfs(step+1)恢复初始状态（回溯的时候要用到）}}
}
● 在算法层面，排列与组合问题本质是一类多分支、多阶段的枚举决策问题，需要在给定元素集合中，按照有序或无序的约束规则逐步筛选、分步构造合法方案。DFS 天然具备分层分支探索、深度遍历与状态回溯的固有特性，可逐层展开多路径选择，深入枚举每一种可行情况。在当前分支搜索完成后，通过回溯复原状态、切换新分支继续求解，天然适配多分支枚举场景，是解决此类多分支决策问题的核心算法。
【算法代码一】
● 这是一个标准的二进制递归生成器，通过深度优先搜索遍历所有可能的组合。它的核心思想是：在每个位置，我们有两种选择（N 或 Y），选择一种后递归处理下一个位置，返回后尝试另一种选择。这种模式是解决组合枚举问题的经典范式。
#include <bits/stdc++.h>
using namespace std;int n;void dfs(int pos,string s) {if(pos>n) {cout<<s<<endl;return;}dfs(pos+1,s+"N");dfs(pos+1,s+"Y");
}int main() {cin>>n;dfs(1,"");return 0;
}/*
in:
3out:
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY
*/● 关键特性解析：dfs(pos, s) 函数中的 s 是按值传递的，这意味着每次递归调用都会创建 s 的一个副本。这天然实现了回溯。即在递归返回后，上一层的 s 保持不变。
例如：在 dfs(2, "N") 中调用 dfs(3, "NN") 后，返回到 dfs(2, "N") 时，s 仍然是 "N"，而不是 "NN"。
模拟执行过程（以 n=3 为例），如下所示。
初始调用：dfs(1, "")
├─ 选择 N (s="N") → dfs(2, "N")
│ ├─ 选择 N (s="NN") → dfs(3, "NN")
│ │ ├─ 选择 N (s="NNN") → dfs(4, "NNN") → 输出 "NNN" ✓
│ │ └─ 选择 Y (s="NNY") → dfs(4, "NNY") → 输出 "NNY" ✓
│ └─ 选择 Y (s="NY") → dfs(3, "NY")
│ ├─ 选择 N (s="NYN") → dfs(4, "NYN") → 输出 "NYN" ✓
│ └─ 选择 Y (s="NYY") → dfs(4, "NYY") → 输出 "NYY" ✓
└─ 选择 Y (s="Y") → dfs(2, "Y")├─ 选择 N (s="YN") → dfs(3, "YN")│ ├─ 选择 N (s="YNN") → dfs(4, "YNN") → 输出 "YNN" ✓│ └─ 选择 Y (s="YNY") → dfs(4, "YNY") → 输出 "YNY" ✓└─ 选择 Y (s="YY") → dfs(3, "YY")├─ 选择 N (s="YYN") → dfs(4, "YYN") → 输出 "YYN" ✓└─ 选择 Y (s="YYY") → dfs(4, "YYY") → 输出 "YYY" ✓【算法代码二】
#include <bits/stdc++.h>
using namespace std;int n;
string s;void dfs(int pos) {if(pos>n) {cout<<s<<endl;return;}s+="N";dfs(pos+1);s.pop_back();s+="Y";dfs(pos+1);s.pop_back();
}int main() {cin>>n;dfs(1);return 0;
}/*
in:
3out:
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY
*/● 关键特性解析
初始调用：dfs(1)，s=""
├─ 追加N，s="N" → dfs(2)
│ ├─ 追加N，s="NN" → dfs(3)
│ │ ├─ 追加N，s="NNN" → dfs(4) → pos>3，输出 NNN
│ │ └─ 回溯删N，追加Y，s="NNY" → dfs(4) → pos>3，输出 NNY
│ └─ 回溯删N，追加Y，s="NY" → dfs(3)
│ ├─ 追加N，s="NYN" → dfs(4) → pos>3，输出 NYN
│ └─ 回溯删N，追加Y，s="NYY" → dfs(4) → pos>3，输出 NYY
└─ 回溯删N，追加Y，s="Y" → dfs(2)├─ 追加N，s="YN" → dfs(3)│ ├─ 追加N，s="YNN" → dfs(4) → pos>3，输出 YNN│ └─ 回溯删N，追加Y，s="YNY" → dfs(4) → pos>3，输出 YNY└─ 回溯删N，追加Y，s="YY" → dfs(3)├─ 追加N，s="YYN" → dfs(4) → pos>3，输出 YYN└─ 回溯删N，追加Y，s="YYY" → dfs(4) → pos>3，输出 YYY
【参考文献】