★부분집합 구하기(DFS)

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

 

입력예제 

3

출력예제

1 2 3

1 2

1 3

1

2 3

2

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

해당 숫자를 사용한다 / 사용하지 않는다. 로 2갈래의 트리가 그려지도록 구현해야한다.

숫자의 사용 여부를 체크해주는 배열이 필요하다.

맨처음은 다 사용하는거(1,2,3) 마지막은 다 사용하지 않는것(공집합)

매개변수로는 부분 집합의 종착점 레벨을 판단하고 사용할 숫자를 지정하는 L로 설정한다.

 

public 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 + " ");
            }
            //공집합 제외하고 출력
            if(tmp.length() > 0) System.out.println(tmp);
        }
        //뻗어나가야 함.
        else {
            //해당 숫자를 사용한다.
            ch[L]=1;
            //왼쪽 뻗기
            DFS(L+1);
            //해당 숫자를 사용하지 않는다.
            ch[L]=0;
            //오른쪽 뻗기
            DFS(L+1);
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        n = 3;
        ch = new int[n+1];
        T.DFS(1);
    }
}