부분집합 구하기 (DFS)

입력예제
3

출력예제
1 2 3
1 2
1 3 
1
2 3
2
3

DFS 이용하기

• 부분집합 개수 공식은 2^n, 이때 1개는 공집합
• 개수당 사용한다/안한다 두 개씩 경우의 수가 나옴
• 깊이우선탐색을 통해 왼쪽 노드들을 쭉 한 번 탐색해주고 이후 순차적으로 탐색
• DFS는 사실상 상태트리 그리는게 제일 중요하다. 상태트리만 만들어지면 원하는 방법에 따라 탐색을 돌려준다

코드 살펴보기

import Foundation

func dfs(_ v: Int) {
    if v == n + 1 {
        for i in 1...n {
            if ch[i] == 1 {
                print(i, terminator: " ")
            }
        }
        print()
    } else {
        ch[v] = 1
        dfs(v + 1)
        ch[v] = 0
        dfs(v + 1)
    }
}

// Reading integer input from standard input
if let input = readLine(), let num = Int(input) {
    let n = num
    var ch = [Int](repeating: 0, count: n + 1)

    dfs(1)
}

• 처음에는 체크 변수를 모두 0으로 초기화
• 이후 dfs함수에서 사용하면 1, 사용하지 않는다는 0으로 표현
• ch(1) 이 1에다 값 1을 넣주고 DFS 함수 돌리기, DFS(2)가 들어가게된다.