计算总和为 x 的所有整数子集（包括负数）

Question

我得到一个最大长度为 40 的数组，其中包含 [-10^9;10^9] 中的整数。我还得到了位于 [0;10^9] 中的预期总和 X。现在我应该给出总和为 X 的子集总数。我想不出一种方法来处理负数。我首先尝试了蛮力方法，它适用于小型输入数组但不适用于大型输入数组：

auto r = 0ULL;
for(auto i = 0ULL; i < (1ULL << n) - 1ULL; ++i) {
    auto x = 0ULL;
    for(auto j = 0ULL; j < n; ++j) {
        if(i & (1ULL << j)) {
            x += values[j];
        }
    }
    r += x == sum;
}
cout << r << '\n';

然后我试着记住加法的中间结果，这样我就不必为相同的元素计算多次。但这会消耗 space 的 ALOT（对于长度为 40 x 的输入，应该约为 9 TB））。有人可以给我一个更好的方法的提示吗？

Answer 1

提示：您可以使用循环。设 num_subsets[i][k] 为 values[0], values[1], ..., values[i] 的子集数，总和为 k。那么

num_subsets[i][k] = num_subsets[i - 1][k – values[i]] + num_subsets[i - 1][k]

那么num_subsets[n-1][x]就是你的答案。

Answer 2

由于内存原因，总和范围和项目计数对于动态规划来说看起来太大了。

但 40 个项目的限制允许应用类似 "meet-in-the-middle" 原则。

分离前 20 个项目并计算所有可能子集的总和 - 只需遍历 2^20 个子集 （包括空子集！）（使用子集编号的递归或二进制表示或其他方式）并在包含对 (sum, count).

的地图中写入总和

下半场同样如此。请注意，地图的大小非常可靠。

遍历第一个地图键并从第二个地图中寻找相应的键。伪代码：

for sum in map1:
    if map2.contains(X - sum):
        result += map1[sum] * map2[X - sum]

计算总和为 x 的所有整数子集（包括负数）

count all subsets of integers (including negative) that sum to x

c++

algorithm

subset-sum