Count number of subsets with sum equal to k

Question

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.

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

Answer 1

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

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

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