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}

Spoofery

Have you tried anything yet? Any first thoughts? – Cajun

Are there negative number in your array ? Integer or float ? Any attempt ? – Photophobia

there exists a polynomial solution for subarrays . Does your subsets mean subarray ? Please give an example . – Jaunita

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].

Shepley

using distance list can help L={1,2,3,0,-3,-5,-6} g=2 then D(g,L) = {-1,0,+1,-2,-5,-7,-8} – Dingy

But this algorithm doesn't count how many subsets. this algorithm only tells you whether there is a solution or not. Even after that and applying backtracking you can derive one solution. Not all the solutions. – Margaret

Answer 2

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; 
}

Huddle

Answer 3

Although the above base case will work fine if the constraints is : 1<=v[i]<=1000

But consider : constraints : 0<=v[i]<=1000

The above base case will give wrong answer , consider a test case : v = [0,0,1] and k = 1 , the output will be "1" according to the base case .

But the correct answer is 3 : {0,1}{0,0,1}{1}

to avoid this we can go deep instead of returning 0 , and fix it by

C++:

if(ind==0)
{
if(v[0]==target and target==0)return 2;  
if(v[0]==target || target==0)return 1; 
return 0 ;
}

Waugh

Answer 4

This is recursive solution. It has time complexity of O(2^n) Use Dynamic Programming to Improve time complexity to be Quadratic O(n^2)

def count_of_subset(arr,sum,n,count):
    if sum==0:
        count+=1
        return count
    if n==0 and sum!=0:
        count+=0
        return count
    if arr[n-1]<=sum:
        count=count_of_subset(arr,sum-arr[n-1],n-1,count)
        count=count_of_subset(arr,sum,n-1,count)
        return count
    else:
        count=count_of_subset(arr,sum,n-1,count)
        return count

Bayadere

is it O(n^2) time or O(n*sum)? – Abirritate

It is Quadratic time i.e. O(2^n) since it is a recursive solution and goes on calculating same problem again and again – Bayadere

you mean exponential? quadratic is power 2. – Abirritate

@GauriShankarBadola yes! – Bayadere

Answer 5

int numSubseq(vector<int>& nums, int target) {
    int size = nums.size();
    int T[size+1][target+1];
    for(int i=0;i<=size;i++){
        for(int j=0;j<=target;j++){
            if(i==0 && j!=0)
                T[i][j]=0;
            else if(j==0)
                T[i][j] = 1;
        }
    }
    for(int i=1;i<=size;i++){
        for(int j=1;j<=target;j++){
            if(nums[i-1] <= j)
                T[i][j] = T[i-1][j] + T[i-1][j-nums[i-1]];
            else
                T[i][j] = T[i-1][j];
        }
    }
    return T[size][target];
}

Lyckman

Answer 6

One of the answer to this solution is to generate a power set of N, where N is the size of the array which will be equal to 2^n. For every number between 0 and 2^N-1 check its binary representation and include all the values from the array for which the bit is in the set position i.e one. Check if all the values you included results in the sum which is equal to the required value. This might not be the most efficient solution but as this is an NP hard problem, there exist no polynomial time solution for this problem.

Modestia

This is a naive solution, not optimal! – Thurman