[JAVA] 자바 부분집합 구하기 이진트리 DFS

1~n까지의 숫자의 부분집합을 모두 구하는 알고리즘을 DFS로 구현해본다.

n=3이라고 가정했을 때 1, 2, 3의 부분집합을 구해보자.

 

위와 같이 해당 숫자를 포함한다, 포함하지 않는다로 이진트리를 만들 수 있다.

ch 배열을 사용해 숫자가 포함되었는지 포함되지 않았는지 확인한 후, 포함된 값들만 출력해주면 된다.

 

 

 

예를 들어, 해당 트리처럼 숫자 1, 2, 3을 포함하는 경로로 DFS(4)에 도달했다면

ch배열은 모두 1의 값을 가지는 형태를 띌 것이고 이를 출력해주면 된다. ==> 부분집합 1 2 3

 

 

다음 예로, 해당 트리처럼 숫자 1, 2는 포함하지만 3은 포함하지 않는 경로로 DFS(4)에 도달했다면

ch배열은 모두 위 그림과 같은 형태를 띌 것이고, 1 값을 갖는 인덱스만 출력해주면 된다. ==> 부분집합 1 2

이런식으로 모든 경로를 반복하다 보면 모든 부분집합들을 출력할 수 있다.

 

 

 

코드

public class Subset {
    static int n;
    static int[] ch;
    public void DFS(int L) {
        if(L==n+1){ //ch배열에서 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; //L 원소를 포함
            DFS(L+1);
            ch[L]=0; //L 원소를 포함X
            DFS(L+1);
        }
    }

    public static void main(String[] args) {
        Subset T = new Subset();
        n=3;
        ch = new int[n+1]; //트리의 max level까지 표현하기 위해
        T.DFS(1);
    }
}

 

 

 

결과

 

 

 

출처 : 인프런 자바 알고리즘 문제풀이 입문 : 코딩테스트 대비