재귀를 사용한 부분 집합 탐색

문제 포인트

• 하나의 자연수 N이 주어졌을 때, 1~N까지의 원소를 갖는 부분집합을 모두 출력해야한다. 이때 공집합의 출력은 제외한다.

입력 예제

3

출력 예제

1 2 3
1 2
1 3
1
2 3
2
3

생각

재귀 함수를 사용하여 이 문제를 풀기 위해서는 상태 트리를 먼저 직접 그려보는 것이 좋다.
입력 예제가 3이므로 3을 예로 상태트리를 그려보면 다음과 같이 그려질 것이다.

• 1의 경우: 1을 원소로 사용한다, 사용하지 않는다의 두가지 갈래로 나뉜다.
• 각 갈래에서 원소에 1을 더한 상태에서 같은 방법으로 각각 두가지 갈래를 나눠 사용하는 경우와 사용하지 않는 경우를 판별한다.
• n + 1의 경우까지 이 과정을 반복한다.

위의 상태 트리를 코드로 구현하면 다음과 같다.

def recursive(value):
    if value == n + 1:  # 입력보다 +1 큰 수에서 탐색 종료하기 때문에
        for i in range(1, n + 1):
            if check[i] == 1:
                print(i, end=" ")
        print()

    else:
        check[value] = 1  # 사용하는 경우
        recursive(value + 1)
        check[value] = 0  # 사용하지 않는 경우
        recursive(value + 1)


n = int(input())
check = [0] * (n + 1)  # 숫자를 사용한다, 하지 않는다 신호를 주기 위해서
recursive(1)

재귀 함수를 사용할 때는 스택에 복귀 주소를 염두에 두는 것이 코드 작성할 때 덜 헷갈리는 것 같다.