046 - 합이 같은 부분집합(DFS)

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

 

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

 

▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

 

▣ 입력예제 1

6
1 3 5 6 7 10

 

▣ 출력예제 1

YES

 

 

 

import sys
# sys.stdin = open('in.txt', 'rt')


# 부분집합의 요소를 확인하면서 합을 비교하는 방식.
def DFS(v):
    if v == n+1:
        sum1 = 0
        for i in range(1, n+1):
            if ch[i] == 1:
                sum1 += a[i-1]

        if sum1 == total-sum1:
            print('YES')
            sys.exit()

    else:
        ch[v] = 1
        DFS(v+1)
        ch[v] = 0
        DFS(v+1)


# 부분집합의 요소를 확인하지 않고 합만 비교하는 방식.
def DFS2(L, sum):
    if sum > total//2:
        return
    if L == n:
        if sum == total-sum:
            print('YES')
            sys.exit(0)
    else:
        DFS2(L+1, sum+a[L])
        DFS2(L+1, sum)


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    ch = [0]*(n+1)
    total = sum(a)
    # DFS와 DFS2 둘중에 하나만 실행가능하다.
    DFS(1)
    # DFS2(0, 0)
    print('NO')