[Algorithm] 부분집합 구하기 (DFS) (Feat. 상태 tree)

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

위의 그림처럼 n이 부분집합으로 사용이 되거나 되지 않을 수도 있다.
이것을 check 리스트를 만들어서 구분하였다.

def DFS(v):
    if v == n+1:
        for i in range(1, n+1):
            if check[i] == 1:
                print(i, end=' ')
        print()
    else:
        check[v] = 1
        DFS(v+1)
        check[v] = 0
        DFS(v+1)


if __name__ == '__main__':
    n = int(input())
    check=[0]*(n+1)  # 부분집합으로 사용 여부
    DFS(1)

깊이 탐색인 것을 다시 되새기면서, check를 1 또는 0으로 바꿔가면서 재귀를 호출한다.

1. 상태 그래프 구현

2. 그래프에 맞춰서 스택으로 생각해보기

3. 코드 구현

ex) D(1)->D(2)->D(3)->D(4)-> ...