Q. 개념

---

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램
을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
▣ 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.
단 공집합은 출력하지 않습니다.
▣ 입력예제 1
3
▣ 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3

전략

• 부분집합의 개수는 2^n이다. (공집합을 제외하려면 2^n-1)

  {1,2,3}에서 하나의 부분집합을 만들기위해 각 원소들을 꺼낼 때, 각 원소는 해당 부분집합에 사용 될 수도, 사용되지 않을수도 있다. (각 원소당 2가지 경우의 수가 존재)

• 상태를 나타내는 이진트리로 구현한다.
  

정답

import java.util.*;
class Main {
	static int n;
	static int[] ch;
	public void DFS(int L){
		if(L==n+1){ // 부분집합 하나 만들어짐
			String tmp="";
			for(int i=1; i<=n; i++){
				if(ch[i]==1) tmp+=(i+" ");
			}
			// 공집합일 경우 출력 X
			if(tmp.length()>0) System.out.println(tmp);
		}
		else{
			// L원소에 대해 사용함(1)을 표시
			ch[L]=1;
			// 가지 뻗기 (ex. 왼쪽) -> 사용 O로 가정
			DFS(L+1);
			
			// L원소에 대해 사용하지않음(0)을 표시
			ch[L]=0;
			// 가지 뻗기 (ex. 오른쪽) -> 사용 X로 가정
			DFS(L+1);
		}
	}

	public static void main(String[] args){
		Main T = new Main();
		n=3;
		// 인덱스 0은 사용하지 않음
		ch=new int[n+1];
		T.DFS(1);
	}	
}