算出所有整数子集（包括负数）的和为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';

然后我试着记住加法的中间结果，这样我就不用为相同的元素计算一次以上。但是这样会消耗大量的空间（对于长度为40x的输入，应该是9TB左右）。谁能给我一个更好的提示？

Answer 1

由于内存的原因，和的范围和项数看起来太大，不适合动态编程。

但是，40项的限制允许应用类似的东西 "中间人见面" 原则。

分开前20项，对所有可能的子集进行数和--只要走过2^20个子集即可 (包括空的！) (使用递归或子集数的二进制表示或其他方式)，并在包含对的图中写出和 (sum, count).

下半场也是这样做的。注意，地图的大小很可靠。

走过第一张地图的键，从第二张地图中寻找对应的键。伪代码。

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

Answer 2

提示： 有一个递归你可以使用。让 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] 就是你的答案。