题解 | #数组分组#

# 这道题是比较折磨的对于递归不熟悉的本人来说
# 1，先将数组分成三个组，five为被5整除的数，three为被3整除的数，other为其他。
# （这里用if和elif就包含了逻辑顺序，即题中所说的先让5去挑，“被3整除的数中不包含5”）
# 2，我们要做到事情很简单，即将other里的元素任意分配给five和three，
# 最终我们检验两个必要条件，other要全部分完，即other的长度为0，并且five和three的和相等
# 3，与递归无关的痛苦在于，怎么分？是的，这似乎没有任何答案说明，这里就是粗暴的枚举法
# （其实个人感觉跟粗暴不搭界源于数学基础），other里的每一个元素，只有两种可能，
# 要么给five要么给three，这样想通了就是2的len(other)次方中可能性，
# 所有的可能性融于计算这种分配的过程，和导致的很多的组合
# 已知3中的计算分配方法，如何求出这些可能呢? 递归就是不断重复一个操作，直到满足我们的一个状态
# 4，既然是other里的每一个元素都人人有份必须二选一的可能抛出去，我们就很容易联想到逐一分配如pop之类
# 5，所以我们设计一个函数叫cal，它的终极任务是，如果判断other为空后，判断两组和是否相同，
# 是则输出True否之相反；那么递归的不满足的开启条件是什么呢？other不为空，只要你不为空，
# 就必须一直重复cal，且一旦发现不为空，就产生两种结果(other抛球给five或者抛给three）



def cal(five,three,other):
    if len(other)==0:
        if sum(five) == sum(three):
            return True
        else:
            return False
    while len(other)>0:
        return cal(five+other[:1],three,other[1:]) or cal(five,three+other[:1],other[1:])

       
while True:
    try:
        n=int(input())
        box = map(int,input().split())
        five,three,other=[],[],[]
        for each in box:
            if each % 5 ==0:
                five.append(each)
            elif each % 3 ==0:
                three.append(each)
            else:
                other.append(each)
        if cal(five,three,other):
            print('true')
        else:
            print('false')
    except:
        break