Binary Tree_부분집합 만들기

🔵 ThingsILearned

✔️ 부분집합의 개수는 2^

공집합 빼면 2^-1

✅ 부분집합 구하기

n이 입력되면 부분집합을 구하세요.
단, 공집합은 출력하지 않습니다.

//⭐️input:
3
//⭐️output:
 1 2 3
 1 2
 1 3
 1
 2 3
 2
 3

🟢 코드

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();
        Scanner sc= new Scanner(System.in);
        n= sc.nextInt(); //⭐️
        ch= new int[n+1];
        T.DFS(1); //call function
    }
}

✔️ static n, ch

static인 이유는 static void main함수에서 n에 접근할 수 있어야 하기 떄문이다.
코드에서 ⭐️있는 n
🔴 처음에 static void main에 있는 n을 새로운 변수로 설정했더니 동작하지 않았다.

    static int n;

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();  //❌
        n= sc.nextInt(); //🔴
        ch= new int[n+1];
        T.DFS(1); //call function
    }

✔️ ch: 부분집합에 포함 될지 안 될지 확인하는 배열

그래서 ch값을 확인해 1이면 부분집합에 포함,
값이 0이면 부분집합에 포함 안 시킴.
ch의 길이가 n+1인 이유는 0번 인덱스는 버리고 1번 인덱스부터 시작하기 때문이다.