问题描述
逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。
输入格式
第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。
输出格式
一个数，最大的长度。
LeetCode 78. 数列子集 + LeetCode 416. 分割等和子集
本题算是LeetCode 416的升级版吧，唯一的不同就是：不是考虑所有的数，而是可以有一些数不取。所以，我就想先求棍子数列的子集吧，再求子集的等和子集。
虽然有点蠢的亚子，还是AC了！
欢迎交流讨论其他方法哦！
n = int(input())
group = list(map(int, input().split()))
#求子集 LeetCode 78
def subsets(nums):
res = [[]]
for i in nums:
res = res + [[i] + num for num in res]
return res
#求等和子集 LeetCode 416
def half_max(nums):
total = sum(nums)
target = sum(nums) // 2
if total % 2:
return False, target
L = [True] + [False] * target
for num in nums:
for i in range(target, num - 1, -1):
L[i] = L[i] or L[i - num]
return L[-1], target
#先设最大长度为0
max_result = 0
#求出子集
nums = subsets(group)
#遍历所有子集，求出子集的等和子集
for nums in nums:
if not nums:
continue
flag, target = half_max(nums)
#可以等分再看该组子集的和是否大于之前
if flag and target > max_result:
max_result = target
print(max_result)
