부분집합 구하기 (DFS)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/iJeD

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

풀이 방법을 잘 모르겠어서 강의를 봤다.

 

#강의 풀이
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)

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

여기서 DFS[v+1] 은 원소를 사용하는것과 안하는것 두가지 길로 나뉘는 것이다.
그래서 사용하는 것을 체크하기위한 배열 ch 를 선언하고
배열의 값이 1인 것의 인덱스만 출력하면 부분집합이 된다.

어렵다. 비슷한 문제를 풀어봐야할것같다.