5.4 부분집합의 합 구하기 - 재귀

0과 양의 정수로 이루어진 집합 N과 양의 정수 X가 있을 때
N의 부분집합 중에 원소의 합이 X인 부분집합이 존재하는지 찾는 문제.
예를 들어 N = {3,2,7,1}, X=6인 경우
부분집합 중 하나인 {3,2,1}의 합이 6이므로 True를 반환.

집합 내의 어떤 원소 P에 대해
1. 부분집합에 P를 포함하면 집합의 나머지에서 합이 X-P가 되는 부분집합을 찾으면 됨.
2. 부분집합에 P를 포함하지 않는다면 집합의 나머지에서 합이 X가 되는 부분집합을 찾으면 됨.

재귀 함수 종료 조건
1. X가 0이 되었는지 확인(성공)
2. 집합 내의 원소를 모두 사용했는지 확인(실패)
3. 원소의 값이 X보다 큰 경우. 재귀 호출하지 않아도 됨(모든 원소는 0과 양의 정수이므로 마이너스가 될 수 없음)

위의 조건들을 가지고 재귀 호출로 구현하면 다음과 같다.

def solve(ar, n, x):
    if x == 0:
        return True
    if n == 0:
        return False
    if ar[0] > x:
        return solve(ar[1:], n - 1, x)

    return solve(ar[1:], n - 1, x) or solve(ar[1:], n - 1, x - ar[0])


if __name__ == '__main__':
    ar = list(map(int, input().split()))
    n = len(ar)
    x = int(input())
    print(solve(ar, n, x))

 

시간 복잡도는 O(2^n).

재귀까지만 구현하고 다음 포스팅에 DP로 구현할 예정.