数组分组

def iscouple(s,left,right):
    #递归终点
    if len(s)==0:
        if sum(left)==sum(right):
            return True
        else:return False
    #数字放在左组或者右组
    for i in range(len(s)):
        news = s[:i]+s[i+1:]
        if iscouple(news,left,right+[s[i]]) or iscouple(news,left+[s[i]],right):
            return True
    return False
while True:
    try:
        n = int(input())
        s = [int(x) for x in input().strip().split()]
    except:
        break
    #初步判断所有数字是否能分成两组,总和不被2整除就不能
    if sum(s)%2!=0:
        print('false')
        continue
    #根据题目要求先将5的倍数放在右组,剩余的数里再将3的倍数放在左组,剩下的放nums里
    left=[]
    right=[]
    nums=[]
    for i in s:
        if i%5==0:
            right+=[i]
        elif i%3==0:
            left+=[i]
        else:
            nums+=[i]
    if iscouple(nums,left,right):
        print('true')
    else: print('false')

"""
只需要一个数字now_sum存储假设存在的两数组总和的差。分组可以假定一数组均加和到now_sum, 二数组均取相反值加和到now_sum。
这样，两数组加和相等的条件就变成了：所有数字加和到now_sum后now_sum=0.
常数级额外空间
"""

def get_res(now_sum, plus, i):
    now_sum += plus * nums[i]    # 只需要一个now_sum记录总和。一数组的加，二数组的减。plus控制加减
    if len(nums) == i+1:    # 到头了返回总和是否为0（两数组加和相等）
        return now_sum == 0
    if nums[i+1] % 5 == 0:    # 5 的倍数必去1数组
        return get_res(now_sum, 1, i+1)
    elif nums[i+1] % 3 == 0:    # 3的倍数必去2数组
        return get_res(now_sum, -1, i+1)
    return get_res(now_sum, 1, i+1) or get_res(now_sum, -1, i+1)    # 深搜

while True:
    try:
        a = int(input())
        nums = list(map(int, input().split()))
        print("true" if get_res(0, 1, 0) or get_res(0, -1, 0) else "false") # 建议牛客优化嗷。太蠢了
    except Exception as err:
        break

def is_group(l3,l5,l,i=-1):
    if i==len(l) and sum(l3)==sum(l5): 
        return True
    elif i==len(l) and sum(l3)!=sum(l5): 
        return False
    else:
#         print(l3,l5)
        i+=1
        return is_group(l3,l5+l[i:i+1],l,i)&nbs***bsp;is_group(l3+l[i:i+1],l5,l,i)
while True:
    try:
        n = int(input())
        nums = list(map(int,input().split()))
        l3 = []
        l5 = []
        l = []
        for i in nums:
            if i%3 == 0:
                l3.append(i)
            elif i%5 == 0:
                l5.append(i)
            else:
                l.append(i)
        if is_group(l3, l5, l):
            print('true')
        else:
            print('false')
    except:
        break

def do(a):
    b = map(int, raw_input().strip().split())
    m3, m5, pos, neg = [], [], [], []
    
    for _ in b:
        if _%5 == 0:
            m5.append(_)
        elif _%3 == 0:
            m3.append(_)
        elif _ > 0:
            pos.append(_)
        else:
            neg.append(_)
    tar = abs(sum(m3)-sum(m5)) # target gap
    cur = sum(pos) - sum(neg) # available max gap
    if tar > cur&nbs***bsp;(cur - tar)%2:
        print 'false'
        return
    tgt = (cur - tar) / 2 # move number will make 2 fold change
    r = [0] * (tgt+1)
    r[0] = 1
    for n in pos+neg:
        n = abs(n)
        for v in range(n, tgt+1):
            r[v] += r[v-n]
    if r[tgt]:
        print 'true'
    
while 1:
    try:
        do(raw_input().strip())
    except Exception as e:
        import traceback
        traceback.print_exc()
        break

def helper(sum3, sum5, count):
    if count==len(others):
        if sum3==sum5:
            return True
        return False
    return helper(sum3+others[count], sum5, count+1)&nbs***bsp;helper(sum3, sum5+others[count], count+1)


while True:
    try:
        n, nums = int(input()), list(map(int, input().split()))
        sum15, sum3, sum5, others = 0, 0, 0, []
        for i in nums:
            if i%15 == 0:
                sum15 += i
            elif i%3 == 0:
                sum3 += i
            elif i%5 == 0:
                sum5 += i
            else:
                others.append(i)
        if sum15:
            print("false")
            continue
        print("true" if helper(sum3, sum5, 0) else "false")
    except:
        break

from itertools import combinations
while True:
    try:
        n = int(input())
        ls = list(map(int, input().split()))
        ls1, ls2, ls3 = [], [], []

        for i in ls:
            if i % 5 == 0:
                ls1.append(i)
            elif i % 3 == 0:
                ls2.append(i)
            else:
                ls3.append(i)
        x = sum(ls)/2 - sum(ls1)
        judge = False
        for i in range(len(ls3)+1):
            ja = 0
            result = set(combinations(ls3,i))
            for j in result:
                if sum(j) == x:
                    judge = True
                    ja = 1
                    break
            if ja == 1:
                 break
        if judge == True:
            print('true')
        else:
            print('false')
    except:
        break

def addup2n(arr, n):     
    if n == 0:
        return True
    if not arr:
        return False
    if arr[0] > 0 and (n < arr[0]&nbs***bsp;n > sum(arr)):
        return False
    if arr[-1] < 0 and (n > arr[-1]&nbs***bsp;n < sum(arr)):
        return False
    if addup2n(arr[1:], n-arr[0])&nbs***bsp;\
            addup2n(arr[1:], n):
        return True
    return False

def find(arr, n):
    if not arr:
        return True if n==0 else False
    sam = sum(arr)
    if sam % 2 != n % 2:
        return False
    gsum = (sam-n) // 2
    return addup2n(sorted(arr), gsum)

while True:
    try:
        n = int(input())
        arr = list(map(int, input().split()))
        five, thr, rem = [], [], []
        for i in arr:
            if i % 5 == 0:
                five.append(i)
            elif i % 3 == 0:
                thr.append(i)
            else:
                rem.append(i)
        dif = abs(sum(five) - sum(thr))
        res = find(rem, dif)
        print('true' if res else 'false')
    except:
        break

while True:
    try:
        def search(resList,subSum):
            if subSum == 0:
                res.append(1)
            else:
                for j in range(len(resList)):
                    search(resList[j + 1:], subSum - resList[j])
        n = int(input())
        nums = list(map(int,input().split()))
        five = []
        three = []
        totalSum = 0
        fiveSum = 0
        threeSum = 0
        for i in range(n):
            totalSum = totalSum + nums[i]
            if nums[i]%5 == 0:
                five = five + [nums[i]]
                fiveSum = fiveSum + nums[i]
            elif nums[i]%3 == 0:
                three = three + [nums[i]]
                threeSum = threeSum + nums[i]
        if (totalSum%2==1):
            print("false")
        elif (fiveSum == totalSum/2) & (threeSum == totalSum/2):
            print("true")
        else:
            resList = []
            for i in range(n):
                if nums[i] not in (five+three):
                    resList.append(nums[i])
            resList.sort()
            target=totalSum//2-fiveSum
            res=[]
            search(resList, target)
            if len(res):
                print("true")
            else:
                print("false")
    except:
        break

def canequalsum(nums):
    if not nums:
        return 'true'
    if sum(nums) % 2 :
        return 'false'
    #分组
    sum5 = [x for x in nums if x % 5 == 0]
    sum3 = [y for y in nums if y not in sum5 and y % 3 == 0]
    num = [x for x in nums if x not in sum5 and x not in sum3]
    sumtotal = sum(nums)
    if (sumtotal - 2 * sum(sum5)) % 2 != 0&nbs***bsp;(sumtotal - 2 * sum(sum3)) % 2 != 0:
        return 'false'
    else:
        target = (sumtotal - 2 * sum(sum5)) // 2
        if target == 0:
            return 'true'
        ans = []
        canmeet(num,target,0,[],ans)
        if ans:
            return 'true'
        else:
            return 'false'
        
def canmeet(num,target,start,temp,ans):
    if target == 0:
        ans.append(temp[:])
        return ans
    for i in range(start,len(num)):
        temp.append(num[i])
        res = target - num[i]
        canmeet(num,res,i + 1,temp,ans)
        temp.pop()

          
while True:
    try:
        n = input()
        nums = [int(x) for x in input().split()]
        print(canequalsum(nums))
    except:
        break

def f(x,z):
    if x in z:
        return True
    else:
        total=False
        for i in range(len(z)):
            xx=z[i]
            yy=z.copy()
            yy.remove(xx)
            total=total&nbs***bsp;f(x-xx,yy)
        return total
while True:
    try:
        n=int(input())
        l1=list(map(int,input().split()))
        a=0
        b=0
        c=[]
        d=0
        for i in range(len(l1)):
            d+=l1[i]
            if l1[i]%5==0:
                a+=l1[i]
            elif l1[i]%3==0:
                b+=l1[i]
            else:
                c+=[l1[i]]
        if d%2!=0:
            print('false')
        else:
            if f(int(d/2-b),c):
                print('true')
            else:
                print('false')
    except:
        break

def search(list,target):
    if target == 0:
        return True
    if not list:
        return False
    return search(list[1:],target) or search(list[1:],target - list[0])

while True:
    try:
        n = int(input())
        num = list(map(int,input().split()))
        a, b, c = [], [], []
        
        for i in num:
            if i % 5 == 0:
                a.append(i)
            elif i % 3 == 0:
                b.append(i)
            else:
                c.append(i)
        
        t = abs(sum(a) - sum(b))
        d = sum(c) - t
        if d % 2 != 0:
            print("false")
        else:
            if search(c,d/2):
                print("true")
            else:
                print("false")
    except:
        break