说明

Given a set of numbers S.
Find maximum sum such that
Sum(A₁) = Sum(A₂)
Where, A₁⊂S and A₂⊂S and A₁⋂A₂=∅
And Sum(X), is the sum of all elements within the set X.

Approach

暴力破解

最简单的方法是：

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)

Time Complexity:O(2^N)
Space Complexity:O(1)

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

Edit:

Limits

1 2 时间限制：60秒（根据所使用的语言而有所不同）

是的，这是NPC问题分区问题

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