본문 바로가기

Algorithm/Python

045 - 부분집합 구하기(DFS)

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

 

 

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

 

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

 

입력예제 1

3

 

출력예제 1

123
12
13

1

23

2
3

 

 

#import sys
#sys.stdin = open('in.txt', 'rt')


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)

 

 

 

 

'Algorithm > Python' 카테고리의 다른 글

047 - 바둑이 승차(DFS)  (0) 2023.08.26
046 - 합이 같은 부분집합(DFS)  (0) 2023.08.25
044 - 이진트리 순회(깊이우선탐색)  (0) 2023.08.25
043 - 재귀함수를 이용한 이진수 출력  (0) 2023.08.24
042 - 최대힙  (0) 2023.08.24