부분집합 구하기(DFS)

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하시오.

public class Practice {
    static int number;
    static boolean[] check;
    public void DFS(int n){
        if (n == number + 1) {
            for (int i = 0; i < check.length; i++) {
                if (check[i]) System.out.print(i + " ");
            }
            System.out.println();
        } else {
            check[n] = true;
            DFS(n + 1);
            check[n] = false;
            DFS(n + 1);
        }
    }
 
    public static void main(String[] args){
        Practice pr = new Practice();
        pr.number = 3;
        check = new boolean[number+1];
        pr.DFS(1);
    }
}

 

위의 코드는 아래와 같은 상태트리 구현으로 작성하였다. 

N을 입력받으면 1부터 시작하여 부분집합에 넣는 경우(O)와 넣지 않는 경우(X)를 DFS로 구현하였다.

숫자 i를 넣는 경우에는 check[i]를 true로 바꾼 상태에서 DFS(i+1)를 호출하였고, 넣지 앟는 경우에는 check[i]를 false로 변경하여 DFS(i+1)을 호출하였다.

만약 DFS(N+1)이 호출된다면 check배열이 true인 값들로만 출력되게 하여서 부분집합의 경우를 모두 나타냈다.