给定一个数组，你必须找到最大可能的两个等和

Question

给定一个数组，你必须找到最大可能的两个相等的总和，你可以排除元素。

即1,2,3,4,6给定数组，我们可以有最大两个相等的和，因为6 2=4 3 1

即 4，10，18， 22，我们可以得到两个相等的总和，因为 18 4 = 22

除了蛮力寻找所有计算并检查两个可能的相等和之外，你解决这个问题的方法是什么？

编辑1:数组元素的最大数目为N

编辑2:这是我的解决方案，https://ideone.com/cAbe4g,，它需要太多的时间，而给定的时间限制是5秒钟，说每种情况。

编辑 3：- 总元素总和不能大于 1000。

Answer 1

对于数组中的每个元素，有三种可能。（i） 将元素包含在第一集合中（ii）将元素包含到第二集合中（iii）不将元素包括在任何集合中，只要第一集合和第二集合的总和等于，则更新答案。

   public class Main
{
    static int ans = -1;
   public static void find(int[] arr,int sum1,int sum2,int start)
   {    if(sum1==sum2)
         ans = Math.max(ans,sum1);
        if(start==arr.length)
          return;
        find(arr,sum1+arr[start],sum2,start+1);
        find(arr,sum1,sum2+arr[start],start+1);
        find(arr,sum1,sum2,start+1);

   }
   public static void main(String[] args)
   {
       int[] arr = new int[]{1,2,100,101,6,100};
       ans = -1;
       find(arr,0,0,0);
       System.out.println(ans);
   }
}

Answer 2

值从0到1000的最大集合（没有两个等和子集）有9个元素，例如：

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512}

如果添加第十个元素，则该元素将等于前九个值的子集之和。

如果您在排除了9个以上的元素后发现两个总和相等的子集，那么可以将排除元素中的两个相等的总和相加以形成更大的相等总和；这意味着您永远不应该排除超过9个元素。

排除元素的总和在0到1000之间。构建一个筛子来检查该范围内的哪些值可以与集合中的元素形成，最多需要50×1000步。（我们可以存储每个总和的最小值，而不是布尔值，并使用该值仅包括9个或更少元素的总和。）

如果我们从小到大查看排除数的总和，这意味着从大到小查看包含数的总和。对于每个排除值的总和，我们检查哪些（最多9个）元素可以形成这个总和（显然不是一个微不足道的步骤，但我们知道元素的数量介于筛子中存储的最小值和9之间），这给了我们排除的集合，因此也给了包含数的集合。然后我们使用类似的筛子技术来检查包含的数字是否可以形成半和；这将在1到500的范围内，最多需要50×500步。

在所有这些中，当然需要考虑奇数/偶数：如果总和是奇数，则必须排除具有奇数和的子集；如果总和是偶数，则只需要排除具有偶数和的子集。

我还没有真正弄清楚如何生成最坏情况输入，因此很难判断最坏情况的复杂性；但我认为一般情况下应该是可行的。

以下是一些正在运行的部分。首先，筛子找到最多9个值的集合的总和，这些值可以排除（并且具有正确的奇数/偶数性），用20个值测试，总和为999：

js prettyprint-override">function excludedSums(values) {
    var sieve = [0];
    for (var i in values) {
        var temp = [];
        for (var j in sieve) {
            if (sieve[j] == 9) continue;
            var val = values[i] + Number(j);
            if (!sieve[val] || sieve[j] + 1 < sieve[val]) {
                temp[val] = sieve[j] + 1;
            }
        }
        for (var j in temp) {
            sieve[j] = temp[j];
        }
    }
    var odd = values.reduce(function(ac, el) {return ac + el}, 0) % 2;
    for (var i in sieve) {
        if (Number(i) % 2 != odd) delete sieve[i];
    }
    return sieve;
}
var set = [40,7,112,15,96,25,49,49,31,87,39,8,79,40,73,49,63,55,12,70];
var result = excludedSums(set);
for (var i in result) document.write(i + ", ");

Answer 3

我建议使用DP解决这个问题，而不是跟踪A，B（两个集合的大小），而是跟踪A B，A-B（两个集合的总和和差）。

然后，对于数组中的每个元素，尝试将其添加到A或B中，或者都不添加。

跟踪和/差的优点在于，您只需要跟踪每个差的单个值，即您所看到的该差的和的最大值。

为了提高效率，我建议您按从小到大的顺序遍历元素，并在达到迄今为止看到的最大差异后停止更新DP。

您还可以只存储差值的绝对值，忽略任何大于25000的差值(因为从这一点开始，差值将不可能返回到0)。

from collections import defaultdict

def max_equal_sum(E):
    D=defaultdict(int)            # Map from abs difference to largest sum
    D[0]=0                        # Start with a sum and difference of 0
    for a in E:                   # Iterate over each element in the array
        D2=D.copy()               # Can keep current sum and diff if element is skipped
        for d,s in D.items():     # d is difference, s is sum
            s2 = s+a              # s2 is new sum
            for d2 in [d-a,d+a]:  # d2 is new difference
                D2[abs(d2)] = max(D2[abs(d2)],s2) # Update with largest sum
        D=D2
    return D[0]/2                 # Answer is half the sum of A+B for a difference of 0

print max_equal_sum([1,2,3,4,6])  # Prints 8
print max_equal_sum([4,10,18,22]) # Prints 22