DFS)부분집합

문제

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

▣ 입력설명 첫 번째 줄에 자연수 N(1<=N<=10)

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

 

▣입력예제 1

3

 

▣ 출력예제 1

 

1 2 3

1 2

1 3

1

2 3

2
3

 

풀이

 

부분집합은 이진트리와 재귀함수를 이용하면 쉽게 풀릴수 있다.

그림과 같이 좌측으로 이동시 해당 체크배열의 값을 1로 우측 이동시 배열의 값을 0으로 설정하고 재귀함수를 호출하여 다시 이동시킨다. 마지막으로 받은값 보다 큰 DFS(4)에서 배열의 값에 따라 값을 출력시키면 원하는 수의 부분집합을 구할수 있다. 

 

코드

 

int check[10]={0};
int level;

void DFS(int num)
{
	if(num>level)
	{
		for(int i=0;i<num;i++)
		{
			if(check[i]==1)cout<<i<<" ";	
		} 
		cout<<endl;
		return;
	}
	else
	{
		check[num]=1;
		DFS(num+1);
		check[num]=0;
		DFS(num+1);
	}
	
}

int main()
{
	cin >> level;
	
	DFS(1);
	


}

 

 

결과