[완전탐색][상태 트리] - 부분집합 구하기(DFS)

문제

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

문제풀이

 

-> 1 2 3 출력

-> 1 2 출력

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


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

• 리스트를 하나 만들어 해당 노드로 가는지 여부를 판단하는 경우를 출력해주면 된다.
• DFS로 먼저 노드의 제일 왼쪽 부분으로 탐색을 한 뒤 다음 노드를 탐색한다. 
• 이때는 조건을 다 돌았을 때 출력을 위해 해당 조건을 탐색할 때 자체에서는 출력이 없다 앞선 탐색 문제와의 다른점이 이 부분이다.
• 탐색시 출력이 언제 되어야 하는지가 관건인듯 하다.