题解 | #分割等和子集#

o1背包问题，体积为sum//2

n = int(input())
a = list(map(int, input().split()))
asum = sum(a)
if asum % 2 == 1:
    print("false")
elif len(a) % 2 == 0 and len(set(a)) == 1:
    print("true")
else:
    v = asum // 2
    dp = [False] * (v+1)
    dp[0] = True
    for i in range(n):
        for j in range(v, a[i] - 1, -1):
            dp[j] = dp[j-a[i]] or dp[j]
    if dp[-1]:
        print("true")
    else:
        print("false")