标准Subset Sum Problem的一个小变化是，我们要从一组N个大小中找到一个K个大小的子集，总和为S。
用于的标准蛮力解产生复杂度O(N ^ K)。但是，以上链接提到了蛮力方法的一种变体，复杂度为O(N ^(K / 2))。
维基文章说
现在基本上它说如果要找到大小为k的子集，我们将所有大小为K / 2的子集以及它们的SUM进行n次哈希计算，并且sum是哈希中的关键，然后检查是否有两组大小为(k / 2)总和为S。
我了解算法，但无法弄清楚如何才能实现它。
散列整数(Sum)，其值是一个列表元组，其中包含实际set的(K / 2)个索引。
我们如何使用C++有效地实现它。使用什么数据结构？
由于大小(k / 2)个元素的SUM可以并且将是唯一的，因此我们不能使用MAP，我们需要一个多图或类似的图。
最佳答案
从基本的O(2 ^ n)蛮力算法开始。
改进的算法，称为中间算法，将输入列表分成相等大小的两半。上半部分采用基本的蛮力算法，其中生成了所有子集，计算了它们的总和，并将其与目标进行了比较。有可能但不太可能在上半年找到目标。如果不是，该算法将生成下半部分的所有子集，并检查每个和，以查看目标和之和是否为上半部分的和，在这种情况下，已找到所需的子集。
我在我的博客上加了一个implementation。
关于c++ - O(2 ^(k/2))时间中K个元素的子总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20357104/