一个算法题，请求哪位大佬指教

[ha2ha]

• 下面是题目

妈妈从超市买了 N 颗糖果来分给两个调皮孩子，但是由于糖果是散装的，每颗糖果的重量可能不一样，如果不能恰好将这 N 颗糖果平分（差一丢都不行，且每颗糖果不可拆分），两熊孩子可能会上房揭瓦。为了保护住宅的完整性，请你判断这 N 颗糖果能否平分，只要两个熊孩子所得糖果的重量总和相等，即为平分。

输入格式: 第一行一个正整数 T(T<20)，表示样例个数。

随后 T 组案例：

第一行一个整数 N ，(2<=N<=100)

第二行 N 个整数，每个数(1<=ai<=100)表示每颗糖果的重量。

输出格式: 对于每个样例，输出 1 表示可平分，否则输出 0 。

输入样例: 2 6 1 1 1 1 1 5 5 2 6 10 7 3 输出样例: 1 0

[eh]

01 背包问题，leetcode 416. 分割等和子集，看看题解吧

[retanoj]

@msg7086
不用排序和反转吧。。
排序和反转是为了先处理大数处理的快么？

[lff0305]

生成函数来解决, n0, n1, n2 ..... nl 如果存在一半的划分, 当且仅当多项式
(1+x^n0)*(1+x^n1)*......*(1+x^nl) 的展开中 x^(sum/2) 的系数不等于 0

写成代码就是

int sum = 0;
for (int i: nums) {
sum += i;
}

if (sum % 2 != 0) {
return false;
}
int[] product = new int[sum + 1];
product[0] = 1;
product[nums[0]] = 1; // 1 + x^num[0]
for (int i=1; i<nums.length; i++) { // product * (1 + x^(nums[i]))
int e = nums[i];
for (int j=product.length - 1; j>=0; j--) {
if (product[j] != 0) {
product[j + e] += product[j];
}
}
}
return product[sum / 2] != 0;

[msg7086]

@retanoj 对，感觉会稍微快一点点。跑 leetcode 测试集，1036 ms → 480 ms 。

[retanoj]

@msg7086
我觉得这个跟测试集有关 ;(
我考虑的是，如果测试样例是排序不友好的，可能在排序那个地方的耗时会凸显出来

[msg7086]

@retanoj 数据集最大就 100 个数字，再怎么说也不会很慢的。
但是算法从大往小跑，找到解的时间比较容易提前。

[ha2ha]

@falsemask 谢谢

[ha2ha]

@milkpuff 谢谢

[ha2ha]

@liuxu 谢谢，但是我只会 java 和 c++，这个没学过，不过我看到题解了，谢谢

[ha2ha]

@msg7086 谢谢

[theOneMe]

其实转变一下思维，就是要找 是否有 x 个数字的和为总糖果和的一半