[Python] 부분집합 구하기 - DFS

DFS(Depth First Search)를 이용하여 부분집합을 구하는 코드를 작성해 봅시다.
근데 '부분집합이 뭐죠?!' 하는 분들을 위해(없겠죠? 없어야함;) 조금 설명할게요.

예를 들어보겠습니다.
자연수 1,2,3을 원소로 갖는 집합 A가 있습니다. 그러면 수학적으로 표현하면 다음과 같습니다.

A={1,2,3}

A의 부분집합은 다음과 같습니다.

∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

총 $2^3$=8개가 나옵니다. 하지만 보통 문제를 낼땐 공집합을 제외한 모든 부분집합을 구하라고 합니다.

근데 위에서 왜 $2^3$=8로 총 부분집합의 개수를 구했을까요?
그 이유는 각 원소별로 부분집합에 1)포함하냐 2)안하냐 -> 2가지의 경우의 수가 생기기 때문에,
2^(원소의 개수)로 총 부분집합의 개수를 구합니다.

이러한 성질을 이용하여 Python 으로 DFS 코드를 작성하면 끝!
참 쉽죠?

여하튼, 공집합을 제외한 모든 부분집합을 구하는 코드를 작성하면 아래와 같습니다.

def DFS(v):
    if v==n+1: #종료지점
        for i in range(n+1):
            if ch[i]==1:
                print(i,end=' ')
        print()
    else:
        ch[v]=1 # 원소 'v' 포함해서 부분집합 만들거야
        DFS(v+1) 
        ch[v]=0 # 원소 'v' 미포함해서 부분집합 만들거야
        DFS(v+1)
        
if __name__=="__main__":
    n=int(input())
    ch=[0]*(n+1) #원소를 사용하는지 안하는지 체크하는 곳
    DFS(1)

오늘의 게시글 끝!