부분집합(MS 인터뷰, DFS:완전탐색) / c / 제한시간 없음

▣ 문제

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

 

▣ 입력설명

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

 

▣ 출력설명

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

 

▣ 입력설명

3

 

▣ 입력설명

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

 

<내 코드>

몰라

감도 안와

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>


int n;
int check[11] = { 0 };
void dfs(int x) {
	if (x == n + 1) {
		for (int i = 1; i <= n; i++) {
			if (check[i] == 1) printf("%d ", i);
		}
		printf("\n");
		return;
	}
	check[x] = 1;
	dfs(x + 1);
	check[x] = 0;
	dfs(x + 1);

}

int main() {

	scanf("%d", &n);
	dfs(1);

	return 0;
}

이 문제를 풀기 위해서는 이진 트리를 완전 탐색하는 방법으로 풀 수 있다.

 

이를 입력예시를 사용해 그림으로 표현하자면 다음과 같다.

 

각 숫자는 트리의 레벨값을 나타낸다.

이진 트리 구조에서 오른쪽 자식은 부분집합으로 포함하고 왼쪽 자식은 부분집합으로 포함하지 않는다.

 

따라서 check[ ]를 처음에 0으로 설정한 후에 오른쪽 노드로 갈때는 1로 바꿔주고 왼쪽 노드로 갈때는 0으로 다시 바꿔준다.

 

dfs 함수 안에서 x가 n+1까지 가면 1값이 들어간 check[ ]의 인덱스를 출력해주고 return을 해준다.

 

.

 

dfs에서 이진 트리를 노드넘버로만 보는것만 알았는데 레벨값으로도 표현할수 있다.