题解 | #分割等和子集#

def inputArr():
    n = int(input())
    arr = list(map(int, input().split()))
    return n, arr


if __name__ == "__main__":
    n, arr = inputArr()
    # 全部元素相加总和
    total = sum(arr)
    # 总和不是偶数或者数组中的最大值大于总和的一半（剩下的全部加起来也不可能等于总和的一半）
    if total % 2 != 0 or max(arr) > total // 2:
        print("false")
    else:
        values = total // 2
        # dp[i]：取值有1或0，1表示在某个数组中的能找到相加等于i的组合
        # 全部初始为0
        dp = [0 for i in range(values + 1)]
        # 数组中只有1个元素，那么当arr[0] = i时，dp[i] = 1
        if arr[0] <= values:
            dp[arr[0]] = 1
        # print(total, values, arr)
        # print(dp)
        for i in range(n):
            # 当j小于arr[i]时，直接就等于上一轮的dp[j]，因为此时不可能取arr[i]
            # 所以第二层循环只用到arr[i]。这样循环中的if语句就不需要了，节约了多余判断的，并减少了循环次数
            for j in range(values, arr[i]-1, -1):
                # if j >= arr[i]:
                    # dp[j] = max(dp[j], dp[j-arr[i]])
                    # dp[j]的值有两种选择：用或者不用arr[i]，如果两者都不能得到j，dp[j]就为0，否则为1
                    dp[j] = dp[j] | dp[j - arr[i]]
            # print(dp)
            # 前面几个元素中，已经有相加等于目标值的组合，后面的元素就没必要再算了，直接打印结果，结束循环
            if dp[-1]:
                print("true")
                break
        else:
            print("false")