부분집합 구하기(DFS)

자연수 n을 입력하면 1~n까지 원소를 갖는 부분집합을 출력하기

 

이진 트리 구조로 간 곳은 체크하면서 n+1에 도달하면 체크된 곳을 출력하기 

왼쪽은 해당 인덱스를 체크하고 오른쪽은 체크하지 않으면서 진행한다

먼저 전역변수로 방문할 배열의 크기와 배열 방문 여부를 체크할 배열을 만들고

 

dfs 함수에서 n+1에 도달하면 방문 체크가 된 곳을 출력하고

아니면 왼쪽은 체크한 후 재귀, 오른쪽은 체크를 하지 않고 순회하게 만들어준다

 

 public void DFS(int L){
        //끝까지 왔으면 체크된 원소를 출력
        if(L == n+1){
            for(int i =1; i < L; i++){
                if(ch[i] == 1) System.out.print(i + " ");
            }
            System.out.println();
        }

        else {
            //왼쪽, 체크 배열 사용
            ch[L] = 1;
            DFS(L+1);
            //오른쪽, 체크 배열 사용 x
            ch[L] = 0;
            DFS(L+1);
        }
    }

전체 코드

import java.util.*;

public class Main{
    static int n;
    //배열 방문 여부를 체크할 배열
    static int[] ch;

    public void DFS(int L){
        //끝까지 왔으면 체크된 원소를 출력
        if(L == n+1){
            for(int i =1; i < L; i++){
                if(ch[i] == 1) System.out.print(i + " ");
            }
            System.out.println();
        }

        else {
            //왼쪽, 체크 배열 사용
            ch[L] = 1;
            DFS(L+1);
            //오른쪽, 체크 배열 사용 x
            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);

    }
}