합이 같은 부분집합

문제 포인트

• 자연수 n과 n개의 원소로 구성된 자연수 집합이 주어짐
• 자연수 집합을 두개의 부분집합으로 나누었을 때, 두 부분집합의 합이 서로 같은 경우가 존재하면 'YES'출력, 그렇지 않으면 'NO' 출력
• 둘로 나뉘는 두 부분집합은 서로소 집합
• 두 부분집합을 합했을 때, 주어진 원래의 집합이 되어야 한다.
• e.g) {1, 3, 5, 6, 7, 10} -> {1, 3, 5, 7} = {6, 10} 이므로 'YES' 출력

n = int(input())
nums = list(map(int, input().split()))
total = sum(nums)


def recursive(level, sum):
    if sum > (total // 2):  # 시간 복잡도 줄이기. 부분집합의 원소 합이 같은것은 전체 원소 합의 절반으로 같다.
        return
    if level == n:  # 종료 조건
        if sum == (total - sum):  # 전체 원소 합에서 부분집합의 합(sum)을 뺀 것은 나머지 원소의 합과 같음
            print("YES")
            sys.exit(0)
    else:
        recursive(level + 1, sum + nums[level])
        recursive(level + 1, sum)


recursive(0, 0)
print("NO")