[JAVA] 알고리즘 : DFS- 부분집합 구하기

 

1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하라.(공집합은 출력하지 않는다.)

 

 

 

 

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);
    }
}