题解 | #数组分组#

这道题其实思路不难，难的就是要尽量简化复杂度。思路逃不开暴力穷举呀！所以要想超圈，出题人只需要把用例好好设计，大家谁都过不了。 降低复杂度的方法有两个： 1、将3和5的倍数先挑出来，在其他的数组里找目标值。 2、暴力穷举时，找到了符合目标值的组合就立即返回，不要再接着找了。

def trace_back(nums,target,temp):
    if sum(temp) == target:
        temp.sort()
        if temp not in res:
            res.append(list(temp))
    else:
        for i in range(len(nums)):
            if len(res) != 0:
                return
            temp.append(nums[i])
            trace_back(nums[:i]+nums[i+1:], target, temp)
            temp.pop()
def isok(part):
    num_5 = 0
    num_3 = 0
    for i in part:
        if i%5 == 0:
            num_5 += 1
        if i%3 == 0:
            num_3 += 1
    if num_5 != 0 and num_3 != 0:
        return False
    else:
        return True
            
def judge(eles):
    #print('eles',eles)
    summary = sum(eles)
    if summary%2 != 0:
        print('false')
        return
    half = summary // 2
    list_3 = []
    list_5 = []
    list_other = []
    for i in eles:
        if i%5 == 0:
            list_5.append(i)
        elif i%3 == 0:
            list_3.append(i)
        else:
            list_other.append(i)
    summary_3 = sum(list_3)
    summary_5 = sum(list_5)
    target = half - summary_3
    #nums = list(eles)
    temp = []
    trace_back(list_other, target, temp)
    if len(res) != 0:
        print('true')
    else:
        print('false')

while True:
    try:
        n = int(input().strip())
        eles = list(map(int,input().strip().split()))
        res = []
        judge(eles)
    except:
        break

#eles = [3,5,8]