59. 부분집합(DFS)

문제

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

출력설명

첫 번째 줄부터 각각의 부분집합을 출력합니다. 부분집합을 출력하는 순서는 출력예제에서 출력한 순서와 같게 합니다. 단 공집합은 출력하지 않습니다.

입력예제

3

출력예제

1 2 3
1 2
1 3
1
2 3
2
3

---

#include <stdio.h>
using namespace std;
int n, i, check[11];

void DFS(int level){
	if(level == n+1){
		for(i=1; i<=n; i++){
			if(check[i] == 1){
				printf("%d ", i);
			}
		}
		puts("");
	} else {
		check[level] = 1;
		DFS(level+1);
		check[level] = 0;
		DFS(level+1);
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	DFS(1);
	
	return 0;
}