题解 | #分割等和子集#

n = int(input())

nums = list(map(int, input().split()))
'''
    也就是说凑够s//2即可
'''
s = sum(nums)
if s & 1 == 1:
    print('false')
else:
    dp = [False] * (s//2+1)
    dp[0] = True
    d = dict()
    for i in range(1, len(dp)):
        d[i] = 1
    for i in range(len(nums)):
        t = list(d.keys())
        for k in t:
            if dp[k-nums[i]]:
                dp[k] = True
                d.pop(k)
    if dp[-1]:
        print('true')
    else:
        print('false')

python 我即使换了True，False的dp最后一组还是超时。。。。

从dp[j] = dp[j] | dp[j-nums[i] 可以看出，当dp[j] 为True时后面迭代的dp[j]一定为True，所以我们只需要关心为False的j就可以了。但这样其实用例太极端的话还是减少不了太多的时间。。。

而且为了方便剔除j，我一开始想用链表做的，结果超时了。。。都是遍历一遍，而且链表还是o1的删除，怎么会超时呢？？