将数组划分为两个等和子集的方法数

Question

问:您已经得到了一系列的值。你必须分A和B两个人，这样：

给A的值的总和与给B. undistributed.

• 的值的总和完全相等，它们都应该至少得到一个值。

• ，可以有一些值留给B.

• 。

输入:值的数组。

输出:确定这样的分发方式的数量。

示例：

Input:[1,2,3,4,5,11]
Answer:8
Possible answers: 
[2,3][5]     
[3,4][5,2]
[2,4,5][11] 
[3,4,5][1,11]
[1,2,3,5][11]
[1,2][3]
[1,3][4]
[1,4][5]

这是在一次面试中向我提出的。我能够使用动态规划在O(n * range_of_sum * range_of_sum)中解决这个问题。但是面试官在时间复杂度(可能是O(n * range_of_sum))方面正在寻找一种更好的方法。

Answer 1

他可能正在寻找的解决方案是填写以下结构。

By Sum(A) - Sum(B)
  By whether A has any values
    By whether B has any values
      Count of ways to get here

对于n步骤，您必须填写一个大小为O(range_of_sum)的数据结构，用于内存、使用O(range_of_sum)和时间O(n * range_of_sum)。