计算总和等于k的子集数 [英] Count number of subsets with sum equal to k

问题描述

给定一个数组，我们需要找出总和等于给定整数k的子集数的计数。
请提出针对此问题的最佳算法。

Given an array we need to find out the count of number of subsets having sum exactly equal to a given integer k. Please suggest an optimal algorithm for this problem. Here the actual subsets are not needed just the count will do.

该数组由可以为负也可以为非负的整数组成。

The array consists of integers which can be negative as well as non negative.

示例：
数组-> {1,4，-1,10,5}绝对和-> 9
{4,5}和{ -1,10}

Example: Array -> {1,4,-1,10,5} abs sum->9 Answer should be 2 for{4,5} and {-1,10}

推荐答案

这是 子集总和问题 ，它是 NP-困难 -因此，没有未知的多项式解决方案。 （实际上，子集总和问题表示很难找到是否有一个子集求和等于给定的总和。）

This is a variation of the subset sum problem, which is NP-Hard - so there is no known polynomial solution to it. (In fact, the subset sum problem says it is hard to find if there is even one subset that sums to the given sum).

解决该问题的可行方法很残酷强制（检查所有可能的子集），或者如果集合包含相对较小的整数，则可以使用伪多项式动态编程技术：

Possible approaches to solve it are brute force (check all possible subsets), or if the set contains relatively small integers, you can use the pseudo-polynomial dynamic programming technique:

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）时空解决方案。

Applying dynamic programming to the above recursive formula gives you O(k*n) time and space solution.

使用 f（n，k）调用[假定数组的索引从1开始]。

Invoke with f(n,k) [assuming 1 based index for arrays].

这篇关于计算总和等于k的子集数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！