06. 부분집합구하기(DFS)

 

설명

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

 

 

 

입출력

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

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.

 

 

 

 

예시

3

 

1 2 3

1 2

1 3

1

2 3

2

3

 

 

 

 

풀이

check배열을 0으로 했다 한단계 내려가고 1로 했다 한단계 내려간다.

import java.util.*;

class Main {
	static int n;
	static int[]check;
	
	public static void DFS(int L) {
		if(L==n+1) {
			String answer="";
			for(int i=1; i<=n; i++) {
				if(check[i]==1) {
					answer+=(i+" ");
				}
			}
			if(answer.length()>0) {
				System.out.println(answer);
			}
	
		}else {
			check[L]=1;
			DFS(L+1);
			check[L]=0;
			DFS(L+1);
		}
		
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n= sc.nextInt();
		check= new int [n+1];
		
		DFS(1);
	}
}