17. Backtracking 활용 - Subste Sum 문제

Subset sum

주어진 집합의 부분집합의 원소 합이 특정 값이 되는 조건을 만족하는 집합을 찾아내는 문제.
모든 집합을 찾아보는 건 2^n개임

DP로 푼다면?(안좋은 예시)

어떤 숫자가 포함될 경우와 그렇지 않은 경우를 모두 재귀적으로 표현

subsetSum(A, i, S): #A는 배열, i는 포함 여부를 살펴보는 수의 인덱스 , S는 특정 값
    if S == 0 : #조건에 맞는 경우
        return True
    elif S < 0 or i == -1 : #조건에 안맞는 경우
        return False 
    else:
        withNum = subsetSum(A, i-1, S-A[i])#A[i]가 부분집합에 포함되는 경우를 백트래킹
        withoutNum = subsetSum(A, i-1, S)#포함되지 않는 경우 백트래킹
        return withNum or withoutNum

즉 subsetSum(A, i, S) = subsetSum(A, i-1, S-A[i]) or subsetSum(A, i-1, S)
마치 dp점화식처럼 보인다.
DP[i][S] = DP[i-1][S-A[i]] or DP[i-1][S]
이 dp테이블을 채우려면 O(n*S)인데 이것은 S가 큰 값으로 주어지면 큰 문제가 생긴다.

백트래킹으로 푼다면?

해당 원소가 부분집합에 포함 여부(1,0)를 기록하는 리스트 x를 사용

subsetSum(k): #인덱스 k의 값이 포함되는지 판단
    currentSum = 현재까지 선택된 원소들의 값
    if k >= len(A):
        if currentSum == S:
            print(X)
    else: #포함 미포함 두가지 가능성 모두 검사
        #A를 오름차순으로 정렬했다고 가정
        if currentSum + A[k] <= S: #A[k]가 포함되려면, 포함했을 때 S보다 작거나 같아야됨
            X[k] = 1
            subsetSum(k+1)
        X[k] = 0
        subsetSum(K+1)