부분집합 구하기

01 May 2023 in Algorithm on Java, Coding, Test

문제

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요.

입력

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

출력

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.

입력예제

3

출력예제

1 2 3
1 2
1 3
1 
2 3 
2
3

해결방법

• 부분 집합을 프린트할 때 중요한 것은 해당 원소를 부분집합으로 프린트 하기 위해 사용 했냐 안했냐를 체크하는 것이다.
• 순회화 마찬가지로 방문을 했냐 안했냐에 따라 진로가 2개로 나뉘어지기 떄문에 이를 체크하여야 한다.

코드

import java.util.*;

class Main {
    static int n;
    static int[] ch;

    public void DFS(int L) {
        // 1부터 시작, 배열의 크기 만큼 반복했으면
        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 {
            // 배열 내 L 을 체크 했다는 의미로 1을 체크
            ch[L] = 1;
            // 다음으로 넘어감.
            DFS(L + 1);
            // 이전 작업이 끝나면 다시 0으로 체크를 풀고 다음을 진행.
            ch[L] = 0;
            // 다음으로 넘어감.
            DFS(L + 1);
        }
    }

    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        n = 3;
        ch = new int[n + 1];
        T.DFS(1);
    }
}