[알고리즘/C++] 부분집합 구하기 - 이진트리 완전탐색 (DFS)

# 문제 설명

자연수 N이 주어지면 1부터 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, ch[10];

// 이진트리를 순회하는 재귀함수입니다.
void DFS(int x){
	if(x>n){
		for(int i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ",i);
		}
		puts("");
	}
	else{
		ch[x]=1;	// 부분집합에 포함되도록 1을 대입하고
		DFS(x+1);	// 왼쪽 노드로 보냅니다.

		ch[x]=0;	// 부분집합에 포함되지 않도록 0을 대입하고
		DFS(x+1);	// 오른쪽 노드로 보냅니다.
	}
}

void main(){
	scanf("%d", &n);
	DFS(1);	
}

n이 3일 때
재귀함수 실행 중 DFS(4)에 도달하면
if( x > n) 이 성립하여
DFS(4)에 도달한 시점의 ch를 순회하며 요소가 1인 경우에 참조값 i를 출력합니다.

위 그림 상의 왼쪽 DFS(4)노드부터 차례대로 실행됩니다.

DFS(4)에 도달할 때마다  
첫 번째에 ch = { 1, 1, 1 }; 이므로 1 2 3 을
두 번째에 ch = { 1, 1, 0 }; 이므로 1 2
세 번째에 ch = { 1, 0, 1 }; 이므로 1 3
네 번째에 ch = { 1, 0, 0 }; 이므로 1
다섯 번째에 ch = { 0, 1, 1 }; 이므로 2 3
여섯 번째에 ch = { 0, 1, 0 }; 이므로 2
일곱 번째에 ch = { 0, 0, 1 }; 이므로 3을 출력하고
여덟 번째에 ch = { 0, 0, 0 }; 공집합이므로 출력하지 않는다.

( for문이 1부터 n까지 순회하므로 ch[0]부터가 아닌
ch[1]=1, ch[2]=1, ch[3]=1 을 {1, 1, 1} 로 표현했습니다 )