[Algorithm] 합이 같은 부분집합 (DFS : 아마존 인터뷰)

sys.exit(0)

-> 프로그램 종료

def DFS(L, sum):  # L은 인덱스 겸 레벨
    if sum > total//2:  # 시간복잡도 줄이기
        return
    if L == n:
        if sum == (total-sum):
            print('YES')
            sys.exit(0)
    else:
        DFS(L+1, sum+a[L])  # 부분집합으로 사용
        DFS(L+1, sum)  # 부분집합으로 사용X


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    total = sum(a)
    DFS(0, 0)
    print('NO')

집합에서 부분집합을 구하면 나머지 원소들도 그들만의 부분집합이 된다.
따라서 합이 같아야 하므로 집합 전체 합 - 부분집합의 합 이 나머지 부분집합의 합이 될 것이다. (주의 : sum == total//2 는 안된다. total이 홀수이면 성립하지 않으므로)

DFS에 인덱스(레벨)과 합을 같이 매개변수로 보낸다.
그러면 check 변수 (부분집합에 포함 시킬 것인지 아닌지를 판단하는 변수)가 없어도 된다.

깊이가 맨 아래로 내려왔을 때, 즉 L == n 일 때 sum을 비교한다.
그렇지 않을 때는 DFS를 재귀호출한다.
이때 부분집합으로 포함하기 위한 재귀호출은 DFS(L+1, sum+a[L])일 것이고, 포함하지 않을 재귀호출은 DFS(L+1, sum)이다.

이렇게 매개변수에 sum을 같이 계산하여 보내면 check변수로 따로 확인하지 않아도 sum을 바로 구할 수 있다.