arrays - 已知子集大小且数组为范围的子集求和问题

Question

我正在尝试通过一些修改找到一种快速解决子集求和问题的方法，我知道获取目标数字所需的子集的确切大小，而且我也知道输入数组的范围是1 到 2000。我的问题是，如果知道这些条件，因为正常解决方案太慢，是否有任何方法可以改进基本子集和问题的解决方案，使其更快。基本上唯一变化的部分是想要的目标总和。

如果可能的话，我希望它返回给定大小的所有可能子集，这些子集加起来等于目标值，而不会降低程序的速度太多。将使用 python 或类似语言的示例代码。

我已经尝试了很多基本子集求和问题的解决方案，但由于输入数组的大小，它们执行起来太慢了。

Answer 1

知道子集的大小是一个非常有用的信息，因为您不必遍历子集大小。

鉴于 N 您的子集大小，您可以:

• 对输入数组的前 N ​​个元素求和(大小为 N 的第一个子集)
• 通过减去子数组的第一个元素并添加其旁边的元素进行迭代，这转化为查看下一个子数组
• 如果总和等于您的目标数，则返回子数组

不管初始数组内容如何，​​这在时间上应该是O(input array size)，在内存上应该是O(1)。使用初始数组的 range 属性可能有更优化的解决方案。

这是 C++ 中的示例:

void subsetSum(std::vector<int>() array, int subArraySize, int targetNumber)
{
    int sum = 0;
    for (int i = 0; i < subArraySize; ++i) // Initial sum
    {
        sum += array[i];
    }
    for (int i = subArraySize; i < array.size(), ++i)
    {
        sum -= array[subArraySize-i];
        sum += array[i];
        if (sum == targetNumber)
            std::cout << subArraySize-i; // this print the starting position of the subarray
    }
}