[인프런] 07_06 부분집합 구하기(DFS)

📖  문제

---

• 첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래 출력예제와 같은 순서로 출력한다.
  • 자연수 N이 주어지면 1 ~ N까지의 원소를 갖는 집합의 부분집합을 모두 출력하시오

출력 예시

 

⚠️  주의사항

---

• 공집합은 출력하지 않는다.

 

✍️  이해

---

/**
 * 1. DFS를 이용해서 풀기 위해 숫자가 주어지면 사용하는 것인지 아닌 것인지 판단
 * 2. 임시배열 temp로 주어진 숫자가 사용하면 1 아니면 0으로 초기화
 * 3. L == N + 1  * +1 인 이유는 3을 입력받았다고 했을 때 4번째까지 가서 확인해야 하기 때문
 *  3-1. answer 초기화
 *  3-2. 1 ~ N 까지 temp[i] == 1 즉 사용하는 칸이면 answeer += i
 *  3-3. 공집합은 출력하지 않으므로 length() > 0 일때면 sout
 */

 

✏️  풀이

---

import java.util.Scanner;

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

---