[문제 출처 : Codechef] 이번에 살펴볼 문제는 다음과 같습니다.

지갑에 다양한 지폐들이 있습니다. 지갑에 있는 지폐들의 조합으로 정확히 $m$원을 낼 수 있을까요? 거스름돈이 생겨서도 안됩니다.

예를 들면, 지갑에 [1, 5, 5]원의 지폐들이 있다고 가정해 봅시다. 그러면 1, 6, 10, 11원을 조합할 수 있습니다. 7원은 만들 수 없겠죠? 결국엔 하나하나씩 조합해 보면서 원하는 조합이 나오는지를 찾아야 합니다. A의 모든 부분집합 출력하기를 참고하시면 좋을 것 같네요 :)

이번에 사용할 방법은 Backtracking이라는 방법입니다. Recursive의 꽃이라고 할 수 있죠 :) 흔히 미로찾기에도 사용되고 정말 광범위하게 사용되는데요, 핵심 원리는 일단 제일 먼저 가능한 것으로 들어간 다음에 모든 가능성을 체크한 다음에 없을 경우 다시 원래대로 돌아와서 다음 가능한 것을 찾는 방식입니다.

backtrack

위의 애니메이션에서 확인할 수 있듯이, 찾다가 벽에 막힌 경우 다시 돌아와서 다음 경로를 탐색하는 것을 보실 수 있죠? 그럼 이와 같은 방식으로 코드를 구현해 보겠습니다.

def isThereSubset(coins, total):
    if total == 0: #만약 조합을 찾았으면 True 리턴
        return True
    if total < 0: #원하는 total을 넘어선 조합이면 False 리턴
        return False
    if len(coins) == 0: #남은 합이 0보다 큰 상태에서 동전이 더 없으면 못찾은 것이다.
        return False

    coin = coins.pop(0) #동전들 중 첫 동전을 뽑는다.
    if isThereSubset(coins, total-coin): #그 동전을 조합에 포함시킨 경우가 성공하면 True를 리턴
        return True
    if isThereSubset(coins, total): #그 동전을 제외한 조합의 경우가 성공하면 True를 리턴
        return True

    ## Backtrack의 핵심적인 부분으로서 반드시 복원을 시켜줘야 합니다~ 그래야 다음 경우를 탐색할 때 누락되지 않으니까요~
    coins.insert(0, coin) #True인 경우를 못 찾았으면 뺐던 coin을 복구시키고 False를 리턴
    return False

그럼 이제 결과가 잘 나오는지 확인해 봅시다.

>>> print isThereSubset([1,1,1], 3)
True
>>> print isThereSubset([1,2,4,8,16], 11)
True
>>> print isThereSubset([1,2,4,8,16], 23)
True
>>> print isThereSubset([1,5,5,10,10], 13)
False
>>> print isThereSubset([17,6,4,998,254,137,259,153,154,3,28,19,123,542,857,23,687,35,99,999], 132)
True

모든 결과가 잘 표시되네요 :) 얼핏 보기에는 쉬워보이나 은근히 많은 연습을 필요로 하는 개념이니 많은 연습으로 숙달해지도록 합시다 :)