[Python Algorithm] 완전탐색(DFS) - 부분집합 구하기

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 

 

 

 

 

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

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

 

 

 

입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

 

출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.

 

입력예제 1
3

 

출력예제 1
1 2 3
1 2
1 3

1

2 3

2
3

 

import sys

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)


n = int(input())
ch = [0]*(n+1)
DFS(1)

 

 

 

⭐️ Point ! ⭐️

• 아래의 그림 + 코드 이해하기 !

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이