题解 | #数组分组#

思路如下：

• 1.将5的倍数和3的倍数分别求和分别记作s5、s3，剩下的数字记作nums
• 2.计算abs(s3-s5)=N，将nums分为两个子集使得子集的求和差值等于N即可

代码如下：

def func(nums, N):  
    # 将nums分为两个子集合,使得其差值正好等于sum3和sum5的差值
    # 假设nums和等于S,两个子集的和分别为：n, S-n
    # 那么S-2n = N => n=(S-N)/2
    # 接下来尝试在nums中找到n即可
    S = sum(nums)  
    n = (S - N) / 2
    if int(n) != n:     # n不是整数，那么肯定无法分出来
        return False
    if n == 0:     #如果n等于0，那么只需要将其中一个子集设置为空即可
    S = sum(nums)  
    n = (S - N) / 2
    if int(n) != n:
        return False
    if n == 0:
        return True
    stack = [[0, 0]]
    while stack:
        s, index = stack.pop()
        for i in range(index, len(nums)):
            s2 = s + nums[i]
            if s2 == n:
                return True
            stack.append([s2, i + 1])


while True:
    try:
        input()
        raw_nums = map(int, input().split())
        s3 = s5 = 0
        nums = []
        for i in raw_nums:
            if i % 5 == 0:
                s5 += i
            elif i % 3 == 0:
                s3 += i
            else:
                nums.append(i)
        nums.sort()
        if func(nums, abs(s3 - s5)):
            print('true')
        else:
            print('false')
    except Exception:
        break