问题如下:
给你一组正整数{a1,a2,a3,...,an},其中没有相同的数字(a1只存在一次,a2只存在一次,......)例如A = {12,5 ,7,91}.问题:是否有两个不相交的A子集,A1 = {b1,b2,...,bm}和A2 = {c1,c2,...,ck},因此b1 + b2 + ... + bm = c1 + c2 + ... + ck?
请注意以下事项:A1和A2不必覆盖A,因此问题不会自动减少到子集求和问题.例如A = {2,5,3,4,8,12} A1 = {2,5}因此A1的总和是7 A2 = {3,4}所以A2的总和是7我们发现A的两个不相交的子集描述的属性,所以问题解决了.
我怎么解决这个问题?我能做的比找到所有可能的(不相交的)子集更好,计算它们的总和并找到两个相等的总和吗?
感谢您的时间.