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

Following is memoized Dynamic Programming code to print the count of the number of subsets with a given sum. The repeating values of DP are stores in "tmp" array. To attain a DP solution first always start with a recursive solution to the problem and then store the repeating value in a tmp array to arrive at a memoized solution.

#include <bits/stdc++.h>

using namespace std; 

int tmp[1001][1001];  


int subset_count(int* arr, int sum, int n) 
{ ` if(sum==0)
        return 1;
    if(n==0)
        return 0;
    if(tmp[n][sum]!=-1)
        return tmp[n][sum];
    else{
        if(arr[n-1]>sum)
            return tmp[n][sum]=subset_count(arr,sum, n-1);
        else{
            return tmp[n][required_sum]=subset_count(arr,sum, n- 1)+subset_count(arr,sum-arr[n-1], n-1);`
        }
    }
} 

// Driver code 

int main() 
{ ` memset(tmp,-1,sizeof(tmp));
    int arr[] = { 2, 3, 5, 6, 8, 10 }; 
    int n = sizeof(arr) / sizeof(int); 
    int sum = 10; `


    cout << subset_count(arr,sum, n); 

    return 0; 
}