枚举子集

题目描述

今有 $n$ 位同学，可以从中选出任意名同学参加合唱。

请输出所有可能的选择方案。

输入格式

仅一行，一个正整数 $n$。

输出格式

若干行，每行表示一个选择方案。

每一种选择方案用一个字符串表示，其中第 $i$ 位为 Y 则表示第 $i$ 名同学参加合唱；为 N 则表示不参加。

需要以字典序输出答案。

样例 #1

样例输入 #1

3

样例输出 #1

NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY

提示

对于 $100\%$ 的数据，保证 $1\le n\le 10$。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
#define MAX 1000
#define Pi 3.14

int a[MAX];
int n;

void dfs(int x){
	if(x==n){
		int i;
		for(i=0;i<n;i++){
			if(a[i]==0) printf("N");
			else printf("Y");
		}
		printf("\n");
		return;
	}
	int j;
	for(j=0;j<=1;j++){
		a[x] = j;
		dfs(x+1);
	}
	return;
}

int main(){
	scanf("%d",&n);
	dfs(0);
	return 0;
}