[Algorithm] 부분집합 구하기(DFS)

문제

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력

해설

부분집합은 1이 포함되는지 안되는지(2가지), 2가 포함되는지 안되는지(2가지)...N이 포함되는지 안되는지..2^n개의 경우의 수로 이루어진다.

포함되는지 안되는지를 나눈 상태트리를 이용한다.

재귀함수를 통해 이진트리(상태트리)를 이용한 DFS 방식을 사용한다.

def dfs(v):
    if v > n:
        for i in range(n+1):
            if check[i] == 1:  # 포함된 것들 출력
                print(i, end=" ")
        print()
        return
    else:
        check[v] = 1   # v 포함
        dfs(v+1)
        check[v] = 0   # v 미포함
        dfs(v+1)


if __name__ == "__main__":
    n = int(input())
    check = [0] * (n+1)
    dfs(1)