[알고리즘]DFS - 부분집합 구하기

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램(공집합은 출력X)

import java.util.Scanner;

public class Subset {
	
	static int n;
	static int[] ch;
	
	public static void DFS(int k) {
		if (k==n+1) {
			String temp = "";
			for (int i=1; i<=n; i++) {
				if (ch[i]==1) temp += (i+" ");
			}
			if (temp.length()>0) System.out.println(temp); // 공집합 출력 X
		}
		else {
			ch[k] = 1; // 왼쪽 방향 // 부분집합에 포함			
			DFS(k+1); 
			
			ch[k] = 0; // 오른쪽 방향 // 부분집합에 포함X
			DFS(k+1);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		ch = new int[n+1];
		DFS(1);
	}

}

---

3
1 2 3 
1 2 
1 3 
1 
2 3 
2 
3