寻找分区问题算法返回 true 的最大值子集

我有以下任务。

您有一个包含 1

假设S有两个子集s1和s2，其中一个子集所有元素的值之和等于另一个子集所有元素值之和，且为最大可能值。我必须返回 S 的哪些元素不会包含在两个子集中的任何一个中。

它可能之前已经解决了，我认为它的一些变体分区问题 https://en.wikipedia.org/wiki/Partition_problem但我找不到它。如果有人能指出我正确的方向，那就太好了。

编辑：一个元素不能同时存在于两个子集中。

这是子集和的变体，可以通过增加问题（和 DP 矩阵）的维数来类似地解决，然后应用与子集和的原始解决方案非常相似的解决方案，该解决方案遵循递归公式：

D(i,x,y) = D(i-1,x,y)   OR    D(i-1,x-l[i],y)    OR    D(i-1,x,y-l[i])
             ^                       ^                       ^ 
           not chosen        chosen for first set         chosen for 2nd set

和基本条款：

D(0,0,0) = true
D(0,x,y) = false        x!=0 or y!=0
D(i,x,y) = false        x<0 or y<0

完成此问题的 DP 矩阵（实际上是 3d 数组）计算后，您所要做的就是查找是否有任何条目D(n,x,x) == true， 对于一些x<= SUM/2 (where SUM是整个原始集合的和），寻找是否存在可行解。
由于您想要最大值，因此答案应该是此类的最大值x that D(n,x,x)=true（因为可能不止一个）

找到解之后就可以找到元素本身（x in D(n,x,x)）通过回溯 DP 矩阵并按照类似问题的解释重新跟踪您的步骤，例如：如何使用背包算法找到袋子里有哪些元素[而不仅仅是袋子的价值]？ https://stackoverflow.com/q/7489398/572670

该解决方案的总复杂度为O(SUM^2 * n)