[Java] 부분집합 구하기

문제

N을 입력하면

1~N을 원소로하는 공집합을 제외한 부분집합을 출력하기

풀이

DFS를 이용해서 풀 수 있다. 예를들어 {1, 2, 3}이라는 집합이 있다고 하자. 이 집합의 공집합을 제외한 부분 집합의 갯수는 2^3-1이므로 7이다. 즉 원소마다 있느냐, 없느냐에따라 경우의 수가 2가지이고 원소의 갯수만큼 그만큼 곱해주면 모든 경우의 수가 나온다. 마지막에 공집합은 제외하니 -1을 하면된다. 그럼 DFS원리를 이용해서 이진트리로 풀어보자

코드

package 인프런.재귀와트리와그래프.부분집합구하기;
/*
* 어떤 집합의 모든 부분집합을 출력하는 문제
* */
public class Main {
    static int n;   // 원소의 갯수
    static boolean[] ch;    // 부분 집합의 원소로 사용했는지 안했는지를 기록하는 배열

    public void DFS(int value) {
        if (value == n+1) {     // 종착점
            String temp = "";
            for (int i=1; i<=n; i++) {
                if (ch[i] == true)
                    temp += (i + " ");
            }
            if (temp.length() > 0)
                System.out.println(temp);
        }
        else {  // 값이 true인 ch 배열의 인덱스 번호를 출력
            ch[value] = true;   // value를 사용한다
            DFS(value+1);   // 왼쪽
            ch[value] = false;
            DFS(value+1);   // 오른쪽
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        n=3;
        ch = new boolean[n+1];  // 인덱스 번호는 해당 값을 의미한다.
        T.DFS(1);
    }
}