합이 같은 부분집합 (DFS)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.
https://inf.run/8dBY

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

 

#강의 풀이
def DFS(L, sum):
    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)

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    total = sum(a)
    DFS(0, 0)
    print("NO")

DFS로 왼쪽, 오른쪽을 번갈아가면서

한쪽은 값을 더하고

한쪽은 더하지않는 방식으로

모든 부분집합의 합을 계산할 수 있다.

 

나는 처음에 DFS 함수안에서 if sum == (totall//2) 를 해도 된다고 생각했으나

DFS 함수안에서 if  sum == (total-sum) 을 하는 이유는

total의 값이 홀수이고 (ex 11) sum의 값이 6이면

sum = 5, total-sum = 6 으로 다르지만

sum = 5,  total//2 = 5 으로 같을 수 있다.