[C++] DFS 부분집합 만들기

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
재귀를 이용한 완전탐색을 하며, 이진트리 전위순회 방식으로 출력한다.  (공집합 제외)

  

#include <stdio.h>
#include <vector>
using namespace std;

int num;
int ch[11] = { 0 };

void dfs(int lv) {
	if (lv == num + 1) {
		for (int i = 1; i <= num; i++) {
			if (ch[i] == 1) {
				printf("%d ", i);
			}
		}
		printf("\n");
		return;
	}
	else {
		ch[lv] = 1;
		dfs(lv + 1);
		ch[lv] = 0;
		dfs(lv+1);
	}
}

int main() {
	scanf("%d", &num);
	dfs(1);
}

DFS를 사용하여 부분집합을 구한다.

이진 트리에서 하나의 vertex 는 1 ~ N 중의 하나의 숫자가 되고

node 는 vertex의 숫자를 포함시킬건지 아닌지를 체크한다.

 

ch 배열은 노드의 역할을 하게 된다. 왼쪽 자식으로 가는 경우에는 부분집합에 포함한다는 의미로 해당 인덱스에 1을 주고, 오른쪽 자식으로 가는 경우에는 포함하지 않는다는 의미에서 해당 인덱스에 0을 준다.

 

인덱스 끝까지 탐색을 마치면 ch 배열에 1을 갖는 값만 출력한다. 

 

이 문제는 직접 그림을 그려보면서 하는 것이 이해하기 쉽다.