1.如果目标数字是x，那么假设它拆分出来的两个部分a和b，如果a==b，那么x的所有位数的和是2a，2a必然是偶数，所以目标各位数字的和必然为偶数，奇数必然拆分不了，输出No
2.按位拆分数字x，将它每一位数按顺序排成数组，数组长度是n，数组的和是t，要想把t拆分成相等的两半，数组的一半必然是一个整数，设为half，如果有一个数大于half，那么必然拆分不了，输出No，如果有一个数等于half，那么数组必然能直接拆分成两半
3.如果以上情况都不成立，那么只能求n个数里取m个数，使m个数的和为half，即变形的背包问题
假设有数组dp，表示和为0~half的目标是否能达成，dp[j]表示和为j的目标是否能达成，存在为True，不存在为False，数组有一个数字是i，遍历dp数组，那么dp[j+i]取决于dp[j]是否能达成，如果能达成，则dp[i+j]一定能达成，即dp[i+j] = dp[j],以此不断更新dp
a = input()
al = [int(x) for x in list(a)] # 拆分每一位，转成数组
t = sum(al) # 对每一位进行求和
if t % 2:
print('No') # 如果所有数字的和是奇数，那么它一定不存在两个子集和等于它
else:
half = t // 2 # 数字和的一半，也就是凑和为half的背包，剩下的自然是另一个背包
flag = 0 # 判断是否可以结束循环
dp = [False for i in range(half + 1)] # 和为0-half的状态表，若m能实现，则dp[m]=True
for i in al:
if i > half: # 如果有一个数大于一半，那么这个目标一定达不成
print('No')
flag = 1
break
elif i == half: # 如果有一个数刚好等于一半，那么这个目标已经达成
print('Yes')
flag = 1
break
else:
dp_copy = dp.copy() # 不能直接更新dp,否则会导致重复累加
for j in range(0, half + 1):
if i + j <= half and dp[j]: # 当前数字是i，如果目标j,即dp[j]可以实现，那么目标i+j，即dp[i+j]一定可以实现
dp_copy[j + i] = True
elif i + j > half:
break
dp = dp_copy
dp[i] = True # 目标为i则可以直接达成
if not flag: # 如果前面已经输出完了这里就不再输出了
print('Yes' if dp[half] else 'No')
京公网安备 11010502036488号