algorithm - 找到两个具有相等总和的子集时出错

Question

我一直在尝试将一个数组分成两个非空的不相交子集，使它们的总和相等。

eg. A = {1,2,3,6,88,55,29}  
one possible answer = 1+2+3  and 6  

我已经阅读了关于平衡分区问题的 mit 教程，但我的限制不同。我不必考虑整个集合 A(意味着 A1 U A2 不一定会导致 A)。另一个问题是 N 的限制。每个元素最多有 100 个不同的元素 (<= 100)。
我也读过THIS与我的问题相关的帖子，但我什么也得不到。

My present Algo -- 
p[1][a[0]] = 1
for i = 2 to n
   for j = 0 to n*n
     if( p[i][j] >= 2) stop

            p[i][j] += j - a[i] > 0 ? ( p[i-1][j] + p[i-1][j-a[i]] ):0
            p[i][j] += j == a[i] ? 1:0
            p[i][j] += j < a[i] ? p[i-1][j]:0  

解释:

Search for sum j at position i. If we got count at position j >=2 means 
there are more than two possibilities for summing up to j. 

HERE is sample working code by me

我知道这种方法无法处理不相交的集合，但我想不出任何其他方法。

我正处于 Dynamic Prog 的学习阶段。我觉得有点困难。有人可以帮我找出我当前算法中的错误吗？

Answer 1

您的代码似乎没有遍历所有子集。 Power Set一组大小为 n 的元素有 2^n-1 个非空元素，所以我认为这是算法复杂度的下限。您需要找到一种适当的方法来枚举子集，如 this other question on SO 所涉及的那样

一般来说，子集的生成是通过一个一个地添加元素来完成的。如果您使用动态规划，这允许您在一次加法中计算单个集合的总和。实际上，如果您有 {1,2,3,6} 并将值保存为 12，则只需添加 88求 {1,2,3,6,88} 的总和。

除了基本 DP 之外，您还可以找到进一步的优化。例如，如果你测试

 {88} > {1,2,3,6,29} 

首先，您不需要使用 {88} 测试 {1,2,3,6,29} 的任何子集(较小的总和) .同时，您不需要使用 {1,2,3,6,29} 测试任何包含 88 的集合，因为它总是会更大...现在需要使用递归从更大的集合到更小的集合。