728x90
분석
풀이
"""
N개의 원소로 구성된 자연수 집합
이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우
{1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10}
"""
import sys
input=sys.stdin.readline
n=int(input())
list = list(map(int, input().split()))
total=sum(list)
def dfs(idx, sum):
if sum>(total-sum)//2: # sum이 홀수인 경우가 있기 때문에 > 체크
return
if idx==n:
if sum==(total-sum):
print("yes")
sys.exit(0) # 종료
else:
dfs(idx+1, sum+list[idx])
dfs(idx+1, sum)
dfs(0,0)
print("NO")
"""
N개의 원소로 구성된 자연수 집합
이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우
{1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10}
"""
import sys
input=sys.stdin.readline
n=int(input())
list = list(map(int, input().split()))
total=sum(list)
ch = [0] * (n + 1)
result="NO"
def dfs(idx):
global result
if idx==n+1 :
sum=0
for i in range(n):
if ch[i] == 1:
sum+=list[i]
if sum==(total-sum):
result="YES"
else:
ch[idx-1] = 1
dfs(idx+1)
ch[idx-1] = 0
dfs(idx+1)
dfs(0)
print(result)
728x90