https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86?tpId=37&tags=&title=&diffculty=0&judgeStatus=0&rp=1

    1. # -*- coding: utf-8 -*-
    2. # !/usr/bin/python3
    3. # 解题思路：先按提干要求构建ls1和ls2，计算ls1和ls2总和之差的绝对值t，用ls3抹平两者差距；
    4. # 问题变成了：ls3的总和减去t之后的值d，d能否被ls3中元素平分。如果d是奇数，那么一定不能平分。
    5. # 如果d是偶数，那么变了成能不能从ls3中挑选出若干元素，他们的和为d/2,与打靶问题有类似之处;
    6. # 但是本题比打靶问题简单，打靶问题每次射击的结果从0到10有11种情况，本地只有两种情况
    7. # 分解子问题：
    8. # 使用递归开始查找，对ls3中的每个元素遍历，每个元素都分两种情况：参与构建d/2和参与构建d/2;
    9. # 形成一个二叉树，记录查找结果;
    10. # 边界条件：
    11. # 1.如果target为0了，那么说明找到了一个构建d/2的方法
    12. # 2.如果ls3都查找完了还没有找到，说明没有办法构建d/2
    13. # 本题也可以使用动态规划实现： dp[i][j]表示ls3中前一个元素能否构建j
    14. # 状态转义方程式：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - ls3[i]]
    16. def search(ll, target):
    17.     # 能不能从从l1中挑出若干元素，是的和为target
    18.     if target == 0:
    19.         return True
    21.     if not ll:
    22.         return False
    23.     # 第一个元素不挑 或者 第一个元素挑
    24.     return search(ll[1:], target) or search(ll[1:], target - ll[0])
    26. while True:
    27.     try:
    28.         m = int(input())
    29.         ls = list(map(int, input().split()))
    31.         ls1 = []
    32.         ls2 = []
    33.         ls3 = []
    35.         for i in ls:
    36.             if i % 5 == 0:
    37.                 ls1.append(i)
    38.             elif i % 3 == 0:
    39.                 ls2.append(i)
    40.             else:
    41.                 ls3.append(i)
    43.         t = abs(sum(ls1) - sum(ls2))
    44.         d = sum(ls3) - t
    45.         if d % 2 != 0:
    46.             print('false')
    47.         else:
    48.             if search(ls3, d/2):
    49.                 print('true')
    50.             else:
    51.                 print('false')
    53.     except:
    54.         break