计算总和等于k的子集数

Question

给定一个数组,我们需要找出具有恰好等于给定整数k的和的子集数量.请为此问题建议最佳算法.这里只需要计数就不需要实际的子集.

该数组由整数组成,可以是负数也可以是非负数.

示例:数组 - > {1,4,-1,10,5} abs sum-> 9 {4,5}和{-1,10}的答案应为2

Answer 1

这是子集和问题的变体,它是NP-Hard - 因此没有已知的多项式解.(事实上​​,子集求和问题表明,如果甚至有一个子集与给定总和相加,则很难找到).

解决它的可能方法是强力(检查所有可能的子集),或者如果集合包含相对较小的整数,则可以使用伪多项式动态编程技术:

f(i,0) = 1    (i >= 0) //succesful base clause
f(0,j) = 0    (j != 0) //non succesful base clause
f(i,j) = f(i-1,j) + f(i-1,j-arr[i])  //step

将动态编程应用于上述递归公式可为您提供O(k*n)时间和空间解决方案.

使用f(n,k)[假设基于1的数组索引] 调用.