💡 Codeing Test/알고리즘

부분집합 구하기(DFS) with python

밈98 2023. 1. 29. 14:11

문제 : 4의 부분집합을 구해보자

 

def DFS(v):
    if v == n + 1:
        for i in range(1, n + 1):
            if checklist[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())
    checklist = [0] * (n + 1)
    DFS(1)

출력값 :

1 2 3 4 
1 2 3 
1 2 4 
1 2 
1 3 4 
1 3 
1 4 

2 3 4 
2 3 
2 4 

3 4