[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 3

⚽ 부분집합 구하기(DFS)

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

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

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

▣ 입력예제 1
3

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

import sys
from collections import deque
import heapq as hq
# sys.stdin = open("input.text", "rt")

N = int(input())

ch = [0] * (N+1)  #1부터 시작하니까 편하게 0번 인덱스 버리고 생각.
def DFS(v):
    if v > N: #종료조건
        #종료조건때 해당 부분집합을 출력해줘야지
        for i in range(1,N+1):
            if ch[i] == 1:
                print(i, end = " ")
        print()
    else:
        ch[v] = 1 #체크한다는 것은 해당 원소를 부분집합에 포함한다는 뜻
        DFS(v+1) 
        ch[v] = 0 #해당 원소 포함하는 모든 경우를 돌고온 후에 이제 포함하지 않는 경우도 생각
        DFS(v+1)

DFS(1)

⚽ 코멘트
DFS는 상태트리를 잘 구성해야해. 이 문제의 경우 현재 노드를 부분집합에 포함할지 말지에 따라서 체크리스트에 값을 표시해서 간단하게 풀 수 있었어.