[알고리즘] 부분집합 구하기(DFS)

 

 

 

전역변수n : 집합의 개수

전역변수 ch: 하나의 부분집합 상태( 해당 숫자의 인덱스가 1이면포함, 0이면 비포함.)

ch[L] = 1: L숫자 포함

ch[L] = 0: L숫자 비포함

static int n; // 전역변수: 집합의 개수
static int[] ch; // 전역변수: 하나의 부분집합 상태( 해당 숫자의 인덱스가 1이면포함, 0이면 비포함.)
public static 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){
    n=3; // 전역변수 n의크기까지 진행
    ch = new int[n+1]; // 인덱스번호가 해당 숫자가 되도록 하기위해 배열사이즈+1
    DFS(1);
}