문제 / 부분집합 구하기 (DFS) / Python 파이썬

문제 제목:  부분집합 구하기 (DFS) 

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

 

---

기본적으로 부분 집합을 구하는 방법

사용하는 상태와 사용하지 않는 상태가 있는 트리 => 상태트리

 

 

 

ch[v] = 1 # 해당 수를 사용 한다 (부분 집합에 포함한다.)

ch[v] = 0 # 해당 수를 사용 하지 않는다 (부분 집합에 포함하지 않는다.)

 

1 2 3 출력함

 

이제 3을 사용하지 않도록 넘어감

 

모범답안

def DFS(v):
    if v == n+1:
        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)
        print()
if __name__ == "__main__":
    n = int(input())
    ch = [0]*(n+1)
    DFS(1)

 

+ DFS 로 만든 부분집합을 하나의 리스트에 입력하기

global 전역변수 사용

def DFS(v):
    global dfs_list
    if v == n+1:
        tmp = []
        for i in range(1, n+1):
            if ch[i] == 1:
                tmp.append(i)
        print(tmp)
        dfs_list.append(tmp)


    else:
        ch[v] = 1
        DFS(v+1)
        ch[v] = 0
        DFS(v+1)
        print()

    return dfs_list

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

출력결과로 공집합이 포함됨을 알 수 있다.

---