您的问题的（决策版本）仍然是NP完整的。这个想法是，如果我们能够解决您的问题，那么（对于每个子集大小）我们可以询问有多少集合的总和小于V，有多少集合的总和小于V-1，这两个数字之差将等于告诉我们子集是否恰好等于V-
因此我们可以解决子集总和问题。[这不是一个完整的证明，因为这是图灵的减少，不是很多减少。]

但是，有一个简单的 动态编程 解决方案可以在时间O（nLV）内运行。[这不能证明P =
NP的原因是V在输入大小上可能是指数的：使用n位，您最多可以表示2 n个值。但是假设您的V不是指数，这不是问题。]

令num [v] [k] [i]表示S的前i个元素的总和为k的大小为k的子集的数量。您可以将其计算为（对于每个i）：

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

其中S [i]是序列中的第i个元素。（任何大小为k的总和等于v要么不使用S [i]，所以将其计为num [v] [k] [i-1]，或者使用S
[i]，这意味着其余的该子集具有k-1个元素，仅使用序列中的前i-1个数字，并求和为vS [i]。）最后，对每个小于V的v计数num [v] [L] [|
S |] ; 那就是你的答案。

另外，如果您仔细地做的话，可以省略第三个下标（对每个i等向下循环）。我只是为了清楚起见包括了它。