[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-합이 같은 부분집합(DFS)

 

 

• 이전의 포스팅과 같이 집합의 원소가 존재하는 경우와 존재하지 않는 경우를 구분하는 이진 트리를 만들어서 응용하면 된다
• 서로소 집합이란 서로 겹치는 원소가 없는 집합을 말한다
• {1,3,5,7}={6,10} 부분집합의 합이 같다는 것은   <전체합 - 왼쪽 부분집합의 합 == 오른쪽 부분집합의 합> 
• ex)  32 - (1+3+5+7=16) =16 (10+6) 
• 또한 두 부분집합의 원소의 합이 같은 경우에 총 집합의 합을 2로 나눈 경우가 그 값이 된다 ex) 1+3+5+..+10=32/2=16

 

import sys
sys.stdin=open("input", "r")
 
 
def DFS(level, sum):
 
    if sum > total//2:                      # 시간 복잡도를 줄이는 방법! 전체 합을 2로 나눈 값이
        return                              # 결국에는 찾고자 하는 값이므로(부분집합의 합이 같은 경우가 존재하는 케이스에서만)
 
    if level==n:
        if sum == (total-sum):
            print("YES")
            sys.exit(0)                     # 같은 경우를 찾았으니까 시스템 종료
    else:
        DFS(level+1, sum+numbers[level])    # o 라서 원소를 더해주는 경우
        DFS(level+1, sum)                   # x 라서 원소를 더하지 않는 경우
 
if __name__=='__main__':
 
    n=int(input())
    numbers=list(map(int, input().split()))
 
    total=sum(numbers)
    DFS(0,0)    #(list의 index겸 이진트리의 level, 부분 집합의 합)
    print("NO")                             # 같은 경우를 못 찾았기 때문에 No를 프린트