Count number of subsets with sum equal to k

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

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

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

Question 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

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

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