부분집합 구하기

생성일: 2022년 1월 29일 오후 6:18

구현 코드 ⭐

# 부분집합 구하기 (DFS)
import sys
sys.stdin = open("input.txt" ,"rt")

def subset(index):
    if index == n+1:
        for i in range(1, n+1):
            if ch[i] == 1:
                print(i, end=' ')
        print()
    else:
        ch[index] = 1
        subset(index+1)
        ch[index] = 0
        subset(index+1)

if __name__ == "__main__":
    n = int(input())
    ch = [0]*(n+1) # 0번째 인덱스는 사용 X
    subset(1)

설명

• DFS의 개념인 밑으로 쭉 탐색하는 형태이다.
• 1부터 시작하여 n 까지의 수들을 각각 출력할 것인지, 하지 않을 것인지에 맞게 2가지 방향으로 트리를 구성한다.
• 출력 여부는 n+1 크기의 배열(0번째 인덱스는 편의상 사용X)을 만들어서 해당 수를 인덱스 번호로 가정하고 값이 0이면 출력 x, 1이면 출력 o 인 구조이다.