[알고리즘] 부분집합 구하기 (DFS)

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

---

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

입력설명

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

출력설명

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.

단 공집합은 출력하지 않습니다.

테스트케이스

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

---

해결방법

위의 트리 형태와 같이 상태트리를 이용하여 문제를 해결

해당 숫자를 이용하나? 혹은 이용하지 않는가? 로 분기를 나누면서 재귀적으로 반복을 한다.

이럴 경우 이용하는지? 이용하지 않는지?를 판단할 수 있도록 상태를 저장하는 리스트가 필요하다.

해당 리스트를 0으로 초기화 시킨 뒤, dfs 재귀함수가 끝나는 지점에 리스트의 정보를 보고 숫자를 출력을 하도록한다.

동작 시각화

---

코드

# dfs 정의
def dfs(x):
    # 종착점 정의
    # 3일 경우 1, 2, 3 까지만 보기 때문에 4일 경우 빠져나온다
    # 종료 지점에서 체크한 것이 1인 것들만 출력 한다
    if x == n+1:
        for i in range(1, n+1):
            if ch[i] == 1:
                print(i, end=' ')
        print()
    else:
        # 원소를 부분 집합으로 사용하겠다. ch가 1일 경우
        ch[x] = 1
        dfs(x+1)
        # 원소를 부분 집합으로 사용하지 않겠다. ch가 0일 경우
        ch[x] = 0
        dfs(x+1)

n = int(input())

# 사용한다 사용 안한다 라는 체크 변수를 생성
# 넉넉하게 +1을 사용 (0,1,2,3) 인덱스를 가진 ch 리스트
ch = [0] * (n+1)

# dfs 사용
dfs(1)