algorithm - 通过将集合分成两个子集来找到可以从集合中形成的最大总和

Question

说明

给定一组数字 S。
找到最大总和使得
总和(A₁) = 总和(A₂)
其中，A₁⊂S 和 A₂⊂S 和 A₁⋂A₂=∅
而Sum(X)，是集合X内所有元素的和。

方法

蛮力

最简单的方法是:

print maximumSum(0,0,0)
def maximumSum(index,sum1,sum2):
  ans=0
  if sum1 == sum2:
    ans=sum1
  if index >= len(S):
    return ans
  m1=maximumSum(index+1,sum1+S[index],sum2)
  m2=maximumSum(index+1,sum1,sum2+S[index])
  m3=maximumSum(index+1,sum1,sum2)
  return max(m,m1,m2,m3)

时间复杂度:O(2^N)
空间复杂度:O(1)

还有比这更好的方法吗？
可选:
我想知道给定的问题是否是 NP 完全问题。

编辑:

限制

1 <= 总和(S) <= 1000000
2 <= len(S) <= 100
时间限制:60 秒(可能因使用的语言而异)

Answer 1

是的，是NPC的问题 Partition Problem

如果集合的和很小，可以看到伪多项式算法部分