2.py

# 69419371
# Сначала необходимо проверить, возможно ли разделить
# сумму входящих значений на 2, т.к. если нельзя, то разбить на две одинаковых
# части невозможно. Если нельзя, то возвращаем False, если можно, то двигаемся
# дальше. Далее необходимо создать массив из булевых значений, равным половине
# суммы входящих значений и прибавить базовый случай в самое начало.
# Все значение изначально будут False, кроме первого, это необходимо для того
# что бы далее производить вычисления. После этого в цикле проходимся по всем
# входящим значениям и во внутреннем цикле проходимся по создаваемому массиву,
# в котором находятся значение от target до текущего взятого элемента из набора
# входящих значений, и во время этого процесса массив из булевых значений будет
# заполняться значениями True, если элемент присутствует во входящих значениях,
# а потом будет производиться проверка, если в нужной ячейке уже написан True,
# при итерации с новым значением, то выставить в последнюю ячейку True,
# т.к. существует необходимая сумма, равная половине сумме всех входящих
# значений. Сделано так же три оптимизации: 1) если в последней ячейки в
# какой-то момент появляется True, то дальнейшие итерации можно не производить
# и вывести True, 2) Если во входящих значениях, есть значение равное половине
# сумме входящих значений, то можно сразу вывести True. 3) Если есть хоть одно
# значение больше половины суммы входящих значений, то можно сразу вывести
# False.
# Временная сложность: O(N*K), где N число элементов во входном множестве, а
# K - сумма элементов
# Пространственная сложность: O(K), где K - сумма элементов

from typing import List


def is_same(nums: List[int]) -> bool:
    nums_sum: int = sum(nums)
    if nums_sum % 2 != 0:
        return False
    target: int = nums_sum // 2
    dp: List[bool] = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        if num == target:
            return True
        if num > target:
            return False
        for j in range(target, num - 1, -1):
            dp[j] = dp[j - num] or dp[j]
            if dp[-1]:
                return True
    return False


def main() -> None:
    _ = int(input())
    nums: List[int] = list(map(int, input().split()))
    print(is_same(nums=nums))


if __name__ == "__main__":
    main()