부분집합 구하기(이진트리탐색 - DFS)

문제

풀이

3을 입력했을 때,

1을 사용하는 경우와 사용하지 않는 경우,
2를 사용하는 경우와 사용하지 않는 경우,
3을 사용하는 경우와 사용하지 않는 경우

총 8가지 경우가 있으며 이 중 셋다 포함되지 않는 공집합은 제외한다.

public class Main {

    static int num;
    static boolean isUsed[];

    public static void main(String[] args) {
        num = 3;
        isUsed = new boolean[num+1];
        dfs(1);
    }

    public static void dfs(int current){
        if(current == num+1){
            print();
        }else{
            isUsed[current] = true; // 사용
            dfs(current+1);
            isUsed[current] = false; // 사용하지 않음
            dfs(current+1);
        }
    }

    public static void print(){
        for(int i = 1; i<isUsed.length; i++){
            if(isUsed[i]) System.out.print(i+" ");
        }
        System.out.println();
    }

}

1을 루트로 사용하여
그 아래로는 차례로 2와 3을 두어 각 숫자가 사용 / 사용하지 않는 경우를 기록하여 말단노드에 도착 시 사용/미사용 데이터를 담은 check배열을 확인하여 집합을 출력한다.