使用 FFT 查找所有可能的固定大小子集和

Question

我需要解决以下问题：给定一个大小为 N 的整数序列 x 和一个子集大小 k，找到所有可能的子集和。子集和是子集中元素的总和。

如果允许 x 中的元素在一个子集（sub-multiset）中出现多次（当然最多 k），则此问题具有通过 FFT 的伪多项式时间解。这是一个例子：

x = [0, 1, 2, 3, 6]
k = 4
xFrequency = [1, 1, 1, 1, 0, 0, 1] # On the support of [0, 1, 2, 3, 4, 5, 6]
sumFrequency = selfConvolve(xFrequency, times = 4) # A fast approach is to simply raise the power of the Fourier series.
sumFrequency > 0 # Gives a boolean vector indicating all possible size-k subset sums.

但是如果一个元素不能在一个子集中多次出现怎么办？

我想出了以下方法，但不确定其正确性。这个想法是首先找到通过添加至少 2 个相同元素而产生的总和的频率：

y = [0, 2, 4, 6, 12] # = [0, 1, 2, 3, 6] + [0, 1, 2, 3, 6] 
yFrequency = [0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1]
sumFrequencyWithRedundancy = convolve(yFrequency, x, x)

我的推理是，由于 y 表示 2 个相同元素的所有可能的和，因此 y + x + x 中的每个和都保证是通过至少添加 2 个相同元素产生的。终于

sumFrequencyNoRedundancy = sumFrequency - sumFrequencyWithRedundancy
sumFrequencyNoRedundancy > 0

有什么错误或者其他解决问题的既定方法吗？

谢谢！

编辑:

经过一些测试，它不起作用。事实证明，除了 sumFrequencyWithRedundancy 之外，还有更多的组合应该从 sumFrequency 中排除，并且组合分析似乎随着 k 迅速升级，最终使其效率低于蛮力求和.

我的动机是在给定无替换和样本大小的情况下找到所有可能的样本总和。然后我想到了通过 FFT 解决标准子集和问题的想法——自由子集大小和不需要的合格子集本身。参考资料在网上很容易找到，基本上是分而治之的方法：

将超集分成左右两部分。
计算左右集合中所有可能的子集和。总和由 2 个布尔向量表示。
对 2 个布尔向量进行卷积。
查找目标总和是否在最终的布尔向量中指示。

您可以了解为什么该算法适用于标准子集和问题。

如果有人能让我知道如何找到所有可能的大小-k 子集总和，我将不胜感激！

Answer 1

给定k和n-元素数组x，足以计算多项式z中的度数-k系数

   n          x[i]
product (1 + y     z).
  i=1

此系数是 y 中的多项式，其中具有非零系数的指数表示可以使用恰好 k 个不同的项形成的总和。

一个策略是用合理平衡的总和拆分 x，评估每一半 mod z^(k+1)，然后使用学校算法进行外部乘法和 FFT（或其他任何) 为内部。这最终应该花费大约 O(k^2 S log^2 S).

有效计算基本对称多项式的想法是由于 Ben-Or。

使用 FFT 查找所有可能的固定大小子集和

Use FFT to find all possible fixed-size subset sums

algorithm

fft

subset-sum